题目：字符串计数

思路：数位dp+hash匹配前后缀

1. 正向：尝试去构造一个包含字符串a，且长度为n的字符串，并统计其数量。做法：按字典序从小到大枚举所有长度为n的字符串，判断字符串a是否在里面。时间复杂度太大，会超时。
2. 反向：尝试构造一个不包含字符串a，且长度为n的字符串，统计其数量res。长度为n的字符串一共有26^n个，因此答案为26^n-res。
3. 从左到右构造字符串，在构造时需要保证当前填入字符位的左边不存在字符串a，并且在确定填入当前位置的字符后不会产生字符串a。例如n=4，a=AB，当前构造的位置为3，那么必须保证第一第二位不是AB，当第二位是A时，那么当前位不能是B。
4. 那么应该怎么去判断当前填入的字符是否会形成一个字符串a呢？可以直接填入选定字符，然后从后往前与a匹配，完全匹配则说明当前字符串不能继续构造了，跳过。
5. 继续观察可以发现，当字符串构造到下标i，当前字符串的后缀与a的前缀最大匹配长度为j时，这种情况统计得到的结果可以复用。例如n=4，a=AB，构造到AA并往下构造的值和构造到BA、CA、DA...的值是一样的。因此可以使用一个二维数组dp记录这些值，下次遍历到下标i，字符串的后缀和a的前缀最大匹配长度为j时，那么值等于dp[i][j]。
6. 怎么计算字符串b的后缀与字符串a的前缀的最大匹配长度？可以使用hash来辅助计算。可以预先计算出a的每一个前缀的哈希值，并用set记录。然后从后往前计算b的后缀的哈希值，如果相等，则更新长度。这里可以优化b的长度，因为a的长度只有100，与其遍历长度n，不如将b截取b的后m个字符进行判断。当然这里也可以使用kmp算法计算。

参考题目：https://leetcode.cn/problems/find-all-good-strings/

代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
	//快速输入
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	//快速输出
	static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
	
	static int mod=1_000_000_007;
	//记录构造到下标i，当前字符串后缀与a前缀最大匹配长度为j的值
	static long[][] dp;
	//用来记录a的前缀哈希值
	static Set<Integer> st;
	//记录长度为m的字符串的后缀与a的前缀的最大匹配长度
	static Map<String, Integer> map;
	//记录p^i，方便哈希值计算
	static int[] h;
	static int p=31;
	//记录当前构造了的字符串
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		String s=br.readLine();
		int n=Integer.parseInt(s);
		s=br.readLine();
		char[] c=s.toCharArray();
		int m=s.length();
		dp=new long[n][m];
		st=new HashSet<Integer>();
		map=new HashMap<String, Integer>();
		h=new int[m];
		for(int i=0;i<n;i++) {
			Arrays.fill(dp[i], -1);
		}
		int pre=0;
		h[0]=1;
		for(int i=0;i<m;i++) {
			pre=pre*p+c[i]-'A'+1;
			st.add(pre);
			if(i>0) {
				h[i]=h[i-1]*p;
			}
		}
		sb=new StringBuilder("");
		long ans=0;
		for(int i=0;i<26;i++) {
			sb.append((char)(i+'A'));
			int id=compare();
			if(id!=m) {
				ans=(ans+dfs(1,('A'+i==c[0]?1:0),n,m,c))%mod;
			}
			sb.deleteCharAt(0);
		}
		long res=(pow(26,n)-ans+mod)%mod;
		pw.println(res);
		pw.flush();
	}
	//快速幂
	private static long pow(int x, int n) {
		if(n==0) {
			return 1;
		}
		long tmp=pow(x,n/2);
		if(n%2==0) {
			return tmp*tmp%mod;
		}
		return tmp*tmp%mod*x%mod;
	}
	//构造字符串，a表示当前构造的下标，b表示当前字符串的后缀与a的前缀的最大匹配长度，n表示题目要求字符串的长度，m是输入的字符串a的长度，c是输入的字符串
	private static long dfs(int a, int b, int n, int m, char[] c) {
		if(a==n) {
			return 1;
		}
		if(dp[a][b]!=-1) {
			return dp[a][b];
		}
		long ans=0;
		for(int i=0;i<26;i++) {
			sb.append((char)(i+'A'));
			int id=compare();
			if(id!=m) {
				ans=(ans+dfs(a+1,id,n,m,c))%mod;
			}
			sb.deleteCharAt(sb.length()-1);
		}
		dp[a][b]=ans;
		return ans;
	}
	//比较当前字符串后缀与a的前缀的最大匹配长度
	private static int compare() {
		String s=sb.toString();
		int m=h.length;
		if(s.length()>m) {
			s=s.substring(s.length()-m);
		}
		if(map.containsKey(s)) {
			return map.get(s);
		}
		char[] ch=s.toCharArray();
		int n=ch.length;
		int hash=0;
		int ans=0;
		for(int i=n-1;i>=0;i--) {
			hash+=(ch[i]-'A'+1)*h[n-1-i];
			if(st.contains(hash)) {
				ans=n-i;
			}
		}
		map.put(s, ans);
		return ans;
	}
}

受益匪浅，大佬强！