[KMP] KMPpractice

[KMP] KMPpractice

文章目录

• T1 [Oulipo](.php?pid=1686)
• T2 [SHT](.php?pid=2594)
• T3 [Compress Words]()
• T4 [Censoring S]()
• T5 [OKR-Periods of Words]()
• T6 [Zoo]()

T1 Oulipo

#include<bits/stdc++.h>
using namespace std;const int NNN=1e6+10;
int T;
char s[NNN],t[NNN];
int nex[NNN],ls,lt;inline void get_next(){for(int i=1,j=0;i<lt;++i){while(j&&t[i+1]!=t[j+1]) j=nex[j];if(t[i+1]==t[j+1]) ++j;nex[i+1]=j;}
}inline void work(){int ans=0;for(int i=1,j=0;i<=ls;++i){while(j&&s[i]!=t[j+1]) j=nex[j];if(s[i]==t[j+1]) ++j;if(j==lt) j=nex[j],++ans;}printf("%dn",ans);
}int main(){scanf("%d",&T);while(T--){scanf("%s%s",s+1,t+1);swap(s,t);ls=strlen(s+1);lt=strlen(t+1);get_next();work();memset(s,0,sizeof(s));memset(t,0,sizeof(t));memset(nex,0,sizeof(nex));}return 0;
}

T2 SHT

#include<bits/stdc++.h>
using namespace std;const int NNN=5e4+10;
char s[NNN],t[NNN];
int nex[NNN],len,ls,lt;inline void get_next(){for(int i=1,j=0;i<len;++i){while(j&&s[i+1]!=s[j+1]) j=nex[j];if(s[i+1]==s[j+1]) ++j;nex[i+1]=j;}
}int main(){while(scanf("%s",s+1)!=EOF){scanf("%s",t+1);ls=strlen(s+1);lt=strlen(t+1);strcat(s+1,t+1);len=strlen(s+1);get_next();if(nex[len]){ls=min(nex[len],min(ls,lt));s[ls+1]='';printf("%s %dn",s+1,ls);}else printf("0n");}return 0;
}

T3 Compress Words

理解一下求出现次数的函数：

for(re int i=1,j=0;i<=n;++i){
while(j&&a[i]!=b[j+1]) j=nex[j];
if(a[i]==b[j+1]) ++j;
if(j==m){printf("%dn",i-j+1);j=nex[j];
}

if(j==m)这一步是模式串走到底的标志
去掉就是模式串走到最长公共前/后缀的位置

#include<bits/stdc++.h>
using namespace std;const int NNN=1e6+10;
int n;
char txt[NNN],t[NNN];
int nxt[NNN],len,ansl,add;inline void get_nxt(){for(int i=1,j=0;i<len;++i){while(j&&t[i+1]!=t[j+1]) j=nxt[j];if(t[i+1]==t[j+1]) ++j;nxt[i+1]=j;}
}inline int get_max(){int j=0;for(int i=max(1,ansl-len+1);i<=ansl;++i){while(j&&txt[i]!=t[j+1]) j=nxt[j];if(txt[i]==t[j+1]) ++j;}return j;
}int main(){scanf("%d",&n);while(n--){scanf("%s",t+1);len=strlen(t+1);get_nxt();add=get_max();for(int i=add+1;i<=len;++i)txt[++ansl]=t[i];}printf("%s",txt+1);return 0;
}

T4 Censoring S

用栈
匹配完之后弹栈
用一个to数组记录跳回去的地方（在该位置匹配成功的j）
然后j就跳过去

#include<bits/stdc++.h>
using namespace std;const int NNN=1e6+5;
char s[NNN],t[NNN];
int nxt[NNN],to[NNN],ls,lt;
int sta[NNN],top;inline void get(){for(int i=1,j=0;i<lt;++i){while(j&&t[i+1]^t[j+1]) j=nxt[j];if(!(t[i+1]^t[j+1])) ++j;nxt[i+1]=j;}
}inline void work(){for(int i=1,j=1;i<=ls;++i){while(j&&s[i]^t[j+1]) j=nxt[j];if(!(s[i]^t[j+1])) ++j;to[i]=j;sta[++top]=i;if(!(j^lt)){top-=lt;j=to[sta[top]];}}
}int main(){scanf("%s%s",s+1,t+1);ls=strlen(s+1);lt=strlen(t+1);get();work();for(int i=1;i<=top;++i)putchar(s[sta[i]]);return 0;
} 

T5 OKR-Periods of Words

有点思维含量

对于最长周期的长度，感到是最大前后缀
手玩样例之后发现最大前后缀（即 n e x t next next）不行&# a b a b a ababa ababa）
考虑 字符串=最大前缀+最小后缀
并且易知最小后缀可以

最小后缀的位置是跳 n e x t next next到 n e x t [ i ] = = 0 next[i]==0 next[i]==0的位置

很明显直接这样跳要T（血的教训，被旁边巨佬嘲笑）
那么用一个 f a i l fail fail记录最小后缀，跳 f a i l fail fail就行了

#include<bits/stdc++.h>
using namespace std;
#define int long longconst int NNN=1e6+10;
int len,nxt[NNN],ans;
char t[NNN];
int fail[NNN];inline void get_nxt(){for(int i=1,j=0;i<len;++i){while(j&&t[i+1]!=t[j+1]) j=nxt[j];if(t[i+1]==t[j+1]) ++j;nxt[i+1]=j;}return;
}signed main(){scanf("%d%s",&len,t+1);get_nxt();for(int i=1;i<=len;++i){if(!nxt[i])continue;int j=nxt[i];if(fail[j]) j=fail[j];//只用跳一次，因为已经fail到底了 fail[i]=j;ans+=i-j;}printf("%lld",ans);return 0;
}

T6 Zoo

显然：

while(nxt[i]){if((nxt[i]<<1)<=len)++num[i];i=nxt[i];}

注意num[1]=1赋初始值

考虑优化
n u m [ i ] = ∑ j = n x t n [ i ] [ j × 2 ≤ i ] ( n u m [ j ] + 1 ) num[i]=sum_{j=nxt_n[i]}[jtimes2leq i](num[j]+1) num[i]=j=nxtn​[i]∑​[j×2≤i](num[j]+1)
那么枚 i i i就行了

#include<bits/stdc++.h>
using namespace std;
#define int long longconst int NNN=1e6+10;
const int MOD=1e9+7;
int T;
char s[NNN];
int nxt[NNN],num[NNN],n;
int res=1;inline void get_nxt(){num[1]=1;for(int i=1,j=0;i<n;++i){while(j&&s[i+1]!=s[j+1]) j=nxt[j];if(s[i+1]==s[j+1]) ++j;nxt[i+1]=j;num[i+1]=num[j]+1;}
}signed main(){scanf("%d",&T);while(T--){scanf("%s",s+1);n=strlen(s+1);get_nxt();for(int i=1,j=0;i<n;++i){while(j&&s[i+1]!=s[j+1]) j=nxt[j];if(s[i+1]==s[j+1]) ++j;while(j>((i+1)>>1)) j=nxt[j];res=(res*(num[j]+1))%MOD;}printf("%lldn",res);res=1;}
}