题解 P5546 【[POI2000]公共串】

· · 题解

题解 P5546 【[POI2000]公共串】

我在知道这个题之前出了一道这 Gen_UNO ，我还是只井底之蛙罢了。

KMP 做法

我们考虑暴力的做法，因为公共串肯定是一个串的子串 （和废话一样），去截取一个串的子串。对与每个串跑 KMP。时间 O(nm^3)，非常爆炸（m 是字符长度）。

你考虑一件这样的事：

我们直接跑 KMP 看匹不匹配，是一个 bool，要这样搞 hash 也能替代。KMP 有一个中途前缀匹配度，前缀匹配度？哦！那我们将本来的子串换成一个串的后缀。因为单调性，[l,r] 可以，肯定 [l,r-1] 可以。这样就一次将所有 l 相等的就统计了，将这个前缀匹配度取 \max。

但这只是一个串是，因为是公共的对于每个串，这个再对这取 \min 。因为这个值只是一个后缀的贡献。所以又要将这个值再取 \max，时间 O(nm^2)，很蓟县。 　

这过程就如 Gen_UNO 中的所说：

他至少需要多少张牌才可以被任何人决斗的情况中得到最少的冰红茶最多

以下是代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,ans=0;
string a[N],cp;
int nxt[N];
void inti(string s){
    nxt[0]=-1;
    for(int i=0,j=-1;i<s.size();){
        if(s[i]==s[j]||j==-1)
            nxt[++i]=++j;
        else
            j=nxt[j];
    }
}
int KMP(string a,string b){
    int ans=-1;
    for(int i=0,j=0;i<a.size();){
        if(a[i]==b[j]&&j==b.size()-1){
            return b.size();
        }
        else if(a[i]==b[j]||j==-1){
            ans=max(ans,j);
            i++;j++;
        }
        else
            j=nxt[j];
    }
    return ans+1;
}
int cheke(string b){
    int ans=1e9;
    inti(b);
    for(int i=1;i<=n;i++)
        ans=min(KMP(a[i],b),ans);
    return ans;
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]; 
    }
    for(int i=0;i<a[1].size();i++){
        string cp="";
        for(int j=i;j<a[1].size();j++)
            cp+=a[1][j];
        ans=max(cheke(cp),ans);
    }
    cout<<ans;
    return 0;
}