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/