本文共 1572 字，大约阅读时间需要 5 分钟。
询问由26个字母组成的长度为n的字符串中含有给定一些字符串为子串的种数。
考虑补集。我们求出不含有给定字符串为子串的种数。
这个问题可以由AC自动机上DP求得。
对给定的串建立AC自动机。我们令dp[i][j]表示字符串第i位走到AC自动机上j节点的方法数。那么对应于一个字符串，就相当于AC自动机走到了某个节点的位置。
现在由于不能包含某些字符串为子串，那么这个子串的end节点一定不能走，fail指针指向这些子串的end节点的节点也不能走。
剩下的就可以进行DP了。那么dp[i][ch[j][k]]+=dp[i-1][j].
# include # include # include # include # include # include # include # include # include # include # include using namespace std;# define lowbit(x) ((x)&(-x))# define pi 3.1415926535# define eps 1e-4# define MOD 10007# define INF 1000000000# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FO(i,a,n) for(int i=a; i PII;typedef vector VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;inline int Scan() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0');}const int N=6010;//Code begin...int trie[N][27], top, fail[N], dp[105][N];void init(){top=1; mem(trie[0],0);}void ins(char *s){ int rt, nxt; for (rt=0; *s; rt=nxt, ++s){ nxt=trie[rt][*s-'A']; if (!nxt) mem(trie[top],0), trie[rt][*s-'A']=nxt=top++; } trie[rt][26]=1;}void makefail(){ int u, v, bg, ed; static int q[N]; fail[0]=bg=ed=0; FO(i,0,26) if ((v=trie[0][i])) fail[q[ed++]=v]=0; while (bg
转载于:https://www.cnblogs.com/lishiyao/p/6704201.html
