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 }
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 }
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 }
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 }