欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

匹配统计

程序员文章站 2022-03-07 20:20:19
传送门:https://www.acwing.com/problem/content/162/(acwing有视频讲解,题解,数据之类的)题意:给你两个字符串a和b,有q次询问,每次询问输出a的所有后缀和b恰好匹配长度为x的后缀个数。题解:这个题好微妙啊,我换了两种思路都不太对。然后看了一下大雪菜老师的视频和(传送门)这个题解,豁然开朗。先求出 b 串的 next 数组,然后a和b......

传送门: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 }

 

本文地址:https://blog.csdn.net/weixin_43735124/article/details/107294602