<span>匹配统计</span>
传送门：https://www.acwing.com/problem/content/162/（acwing有视频讲解，题解，数据之类的）
题意：给你两个字符串a和b，有q次询问，每次询问输出a的所有后缀和b恰好匹配长度为x的后缀个数。
题解：这个题好微妙啊，我换了两种思路都不太对。然后看了一下大雪菜老师的视频和（传送门）这个题解，豁然开朗。
先求出 b 串的 next 数组，然后a和b串进行匹配。a 串遍历用 i，b串用 j，j 正好是b串能匹配以 i 为结尾的a串的长度，所以就是以 i-j+1 为头的串。根据 kmp 中 next 数组的性质以 i-next[j]+1 的串和 b 恰好匹配的长度也为 j，然后依次套娃...直到 next[j]==-1 结束，用 res[j] 记录。但是这样套娃时间复杂度太大了O(nm)（菜鸡不会算嘤嘤嘤，借助大佬的时间复杂度），其实这就是一个拓扑的结构，只要最后记录完之后在算就会节省很多时间。res[x] 记录的是匹配的前缀至少为 x 的后缀数量，但我们要求的是恰好为x的数量，所以减去 res[x+1] 就是答案了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int nt[200100]; 5 int res[200100]; 6 map<int,int>p; 7 8 void getnext(string p) 9 { 10 nt[0]=-1; 11 int i=0,j=-1; 12 int len=p.size(); 13 while(i<len){ 14 if(j==-1||p[i]==p[j]){ 15 i++,j++; 16 nt[i]=j; 17 } 18 else j=nt[j]; 19 } 20 } 21 22 void kmp(string t,string p) 23 { 24 getnext(p); 25 int i=0,j=0; 26 int lt=t.size(),lp=p.size(); 27 while(i<lt){ 28 if(j==-1||t[i]==p[j]){ 29 i++,j++; 30 res[j]++; 31 } 32 else j=nt[j]; 33 } 34 } 35 36 int main() 37 { 38 ios::sync_with_stdio(false); 39 cin.tie(0); 40 cout.tie(0); 41 int n,m,t; 42 cin>>n>>m>>t; 43 string a,b; 44 cin>>a>>b; 45 kmp(a,b); 46 for(int i=n;i>=1;i--) res[nt[i]]+=res[i]; 47 while(t--){ 48 int x; 49 cin>>x; 50 cout<<res[x]-res[x+1]<<endl; 51 } 52 return 0; 53 }
CVTE公司福利 265人发布