当前位置：首页 > news >正文

蓝书2.2 KMP算法

news 来源：原创 2024/5/3 14:10:50

T1 Radio Transmission bzoj 1355

题目大意：

一个字符串，它是由某个字符串不断自我连接形成的

但是这个字符串是不确定的，现在只想知道它的最短长度是多少

思路：

kmp 输出n-nxt[n]

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #include<set>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 1000100
13 const int MOD=1e9+7;
14 const int bas=2333;
15 using namespace std;
16 inline int read()
17 {
18     int x=0,f=1;char ch=getchar();
19     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
20     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
21     return x*f;
22 }
23 int n,nxt[MAXN];
24 char ch[MAXN];
25 int main()
26 {
27     n=read();scanf("%s",ch+1);
28     for(int j=0,i=1;i<=n;i++)
29     {
30         while(ch[i+1]!=ch[j+1]&&j) j=nxt[j];
31         if(ch[i+1]==ch[j+1]) j++;
32         nxt[i+1]=j;
33     }
34     printf("%d",n-nxt[n]);
35 }

View Code

T2 OKR-Periods of Words bzoj 1511

题目大意：

求一个串的所有前缀的最长周期(不算自己)长度之和

思路：

求出nxt后不断向前跳用i减去跳过之后的nxt

不能用最短循环节累计的例子： abcdaa

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #include<set>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 1000100
13 const int MOD=1e9+7;
14 const int bas=2333;
15 using namespace std;
16 inline int read()
17 {
18     int x=0,f=1;char ch=getchar();
19     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
20     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
21     return x*f;
22 }
23 int n,nxt[MAXN];
24 ll ans;
25 char ch[MAXN];
26 int main()
27 {
28     n=read();scanf("%s",ch+1);
29     for(int j=0,i=1;i<=n;i++)
30     {
31         while(ch[i+1]!=ch[j+1]&&j) j=nxt[j];
32         if(ch[i+1]==ch[j+1]) j++;
33         nxt[i+1]=j;
34     }
35     for(int i=1;i<=n;i++)
36     {
37         if(!nxt[i]) continue;
38         while(nxt[nxt[i]]) nxt[i]=nxt[nxt[i]];
39         ans+=i-nxt[i];
40     }
41     printf("%lld",ans);
42 }

View Code

T3 似乎在梦中见过的样子 bzoj 3620

题目大意：

找出串中所有形如A+B+A的子串 len(A)>=k,len(B)>=1

思路：

每个点为起始点做n遍kmp

每个终止点只需要判断是否存在nxt使border大于等于k且小于子串长度一半

奇奇怪怪的复杂度

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #include<set>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 15100
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 int n,nxt[MAXN],k;
22 ll ans;
23 char ch[MAXN];
24 int main()
25 {
26     scanf("%s",ch+1);n=strlen(ch+1),k=read();
27     for(int t=1;t+2*k<=n;t++)
28     {
29         nxt[t-1]=nxt[t]=t-1;
30         for(int j=t-1,i=t;i<=n;i++)
31         {
32             while(ch[i+1]!=ch[j+1]&&j>=t) j=nxt[j];
33             if(ch[i+1]==ch[j+1]) j++;
34             nxt[i+1]=j;
35         }
36         for(int i=t+2*k;i<=n;i++)
37         {
38             int x=nxt[i];
39             while(2*(x-t+1)>=i-t+1) x=nxt[x];
40             if(x-t+1>=k) ans++;
41         }
42     }
43     printf("%lld",ans);
44 }

View Code

T4 Censoring bzoj 3942

题目大意：

有一个S串和一个T串，长度均小于1,000,000，设当前串为U串，然后从前往后枚举S串一个字符一个字符往U串里添加，若U串后缀为T，则去掉这个后缀继续流程

输出最后的S串

思路：

先nxt处理T 然后用一个手打栈记录U串

记录每个位置匹配到T的位置

匹配即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #include<set>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 1100100
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 int n,m,nxt[MAXN],top,pos[MAXN];
22 ll ans;
23 char ch[MAXN],s[MAXN],st[MAXN];
24 int main()
25 {
26     scanf("%s",s+1);scanf("%s",ch+1);
27     n=strlen(s+1),m=strlen(ch+1);
28     for(int j=0,i=1;i<=m;i++)
29     {
30         while(ch[i+1]!=ch[j+1]&&j) j=nxt[j];
31         if(ch[i+1]==ch[j+1]) j++;
32         nxt[i+1]=j;
33     }
34     for(int j=0,i=1,x;i<=n;i++)
35     {
36         st[++top]=s[i],pos[top]=pos[top-1];
37         while(st[top]!=ch[pos[top]+1]&&pos[top]) pos[top]=nxt[pos[top]];
38         if(st[top]==ch[pos[top]+1]) pos[top]++;
39         if(pos[top]==m) top-=m;
40     }
41     for(int i=1;i<=top;i++) printf("%c",st[i]);
42 }