题意：
给出一个长度为1 e 5的字符串和n ( n < = 1 e 5 )个长度< = 30的子串，求每个子串在模式串中的最大不相交出现次数；
思路：
大概是A C自动机模板题？
下面说一下哈希的做法：
有一个很重要的地方就是子串的长度是< = 30的，也就是说我们完全可以枚举模式串中长度为[ 1 , 30 ]的字符串，通过比较哈希值来看这段字符串是不是子串，时间复杂度大概O ( 30 n )
这样没有办法处理的问题就是如何保证不相交了。
设l a s [ x ]表示哈希值为x的字符串在模式串中的上一个出现位置(记录的是尾端字符所在的位置)。比如a b a b a b，当枚举到i = = 1的时候，子串为a b ， l a s [ ′ a b ′ ] = 2
这样每次遍历的时候，只需要判断l a s [ n o w ] < i
简单说一下正确性，这样处理的目的是避免相交的子串，但是怎么能够保证这样是最优的呢？
如果有某个子串出现了奇数次，比如b a b a b a b，其中b a b出现了3次，按照上述算法，中间的b a b会被忽略掉，最后答案为2 次；
如果有某个子串出现了偶数次，比如b a b a b a b a b ，其中b a b 出现了4 次，按照上述算法，第二个和第四个的b a b会被忽略掉，最后答案为2次；
这两种都是最优的。
代码：
const int N=4e5+7,P=131; ull h[N], p[N],a[N]; char str[N]; ull th[50],tp[50]; ull get(int l, int r) { return h[r]-h[l-1]*p[r-l+1]; } int main(){ int _=read; while(_--){ scanf("%s",str+1); p[0]=1;h[0]=0; int len=strlen(str+1); for(int i=1;i<=len;i++){ h[i] = h[i - 1] * P + str[i]; p[i] = p[i - 1] * P; //cout<<h[i]<<endl; } unordered_map<ull,int>mp,las; int n=read; rep(i,1,n){ char s[35];cin>>s+1; tp[0]=1;th[0]=0; for(int j=1;j<=strlen(s+1);j++){ th[j]=th[j-1]*P+s[j]; tp[j]=tp[j-1]*P; } a[i]=th[strlen(s+1)]; mp[a[i]]=0; las[a[i]]=0; //cout<<a[i]<<endl; } for(int i=1;i<=len;i++){ for(int j=0;j<30&&i+j<=len;j++){ ull now=get(i,i+j); //if(i==1&&j==2) cout<<now<<endl; if(mp.count(now)){ if(las[now]<i) mp[now]++,las[now]=i+j; } } } rep(i,1,n) printf("%d\n",mp[a[i]]); } return 0; }
