KMP求最小覆盖子串
KMP求最小覆盖子串
问题描述:
给定一个字符串,要求在线性时间内找到一个最小的子串S,使得S在无限复制扩张能够覆盖原串
例如
Input
ABABA
Output
2
BA
思路
观察样例可以发现,其实最小覆盖子串可以是AB也可以是BA,也就是说最小覆盖子串的所有循环同构子串也可以成为答案,由于KMP匹配的是后缀,因此一般从后向前取
最小覆盖子串的长度为 n-Next[n]其中n为字符串的长度
原理也很简单:
A GF C BE D
***************************** 原字符串
------------------
------------------
其中,B=Next[D],因此[A,B]=[C,D],[E,D]=[F,B],[A,G]=[C,B],此时[E,D]即为一个覆盖子串,假设还有更小的覆盖子串,则不满足Next数组最大性
代码
void getNext(int n){
memset(Next,0,sizeof Next);
for (int i=2,j=0;i<=n;++i){
while (j && has[i]!=has[j+1]) j=Next[j];
if (has[i]==has[j+1]) j++;
Next[i]=j;
}
ans=n-Next[n];
}
例题
goto
先做一次哈希,把每一行转换为数字,将得到的hash值计算最小覆盖子串,然后把每一列转换为数字,同样的操作,将两次的结果相乘即可
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
char s[10005][80];
int n,m,Next[10005],ans=1;
ULL p=131,has[10005];
void getNext(int n){
memset(Next,0,sizeof Next);
for (int i=2,j=0;i<=n;++i){
while (j && has[i]!=has[j+1]) j=Next[j];
if (has[i]==has[j+1]) j++;
Next[i]=j;
}
ans*=n-Next[n];
}
int main(){
cin>>n>>m;
for (int i=1;i<=n;++i) scanf("%s",s[i]+1);
for (int i=1;i<=n;++i){
has[i]=0;
for (int j=1;j<=m;++j){
has[i]=has[i]*p+s[i][j]-'A'+1;
}
}
getNext(n);
for (int i=1;i<=m;++i){
has[i]=0;
for (int j=1;j<=n;++j){
has[i]=has[i]*p+s[j][i]-'A'+1;
}
}
getNext(m);
cout<<ans<<endl;
return 0;
}
KMP求最小循环子串
与前面问题的区别是,这里的循环子串必须是在有限次扩张后正好覆盖原串的
[post cid=”78” /]
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接:https://hs-blog.axell.top/archives/97/