KMP蒟蒻求助
  • 板块CF25E Test
  • 楼主Alea
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/25 23:41
  • 上次更新2023/12/26 13:57:40
查看原帖
KMP蒟蒻求助
322792
Alea楼主2023/12/25 23:41

代码如下:

#include <bits/stdc++.h>
using namespace std;
vector<int> getfail(string s){
    int n=s.length();
    vector<int> fail(n,0);
    for(int i=1;i<n;++i){
        int j=fail[i-1];
        while(j>0&&s[i]!=s[j]) j=fail[j-1];
        if(s[i]==s[j]) ++j;
        fail[i]=j;
    }
    return fail;
}
int combin(string a,string b,string c){
    return a.length()+b.length()+c.length()-getfail(b+a)[b.length()+a.length()-1]-getfail(c+b)[c.length()+b.length()-1];
}
int main(){
    int ans=0x3f3f3f3f;
    string sss[4];
    int per[4]={0,1,2,3};
    for(int i=1;i<=3;++i) cin>>sss[i];
    do{
        ans=min(ans,combin(sss[per[1]],sss[per[2]],sss[per[3]]));
    }while(next_permutation(per+1,per+4));
    cout<<ans<<endl;
    return 0;
}
2023/12/25 23:41
加载中...