WA on #6
  • 板块CF25E Test
  • 楼主Peizekai
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/31 23:46
  • 上次更新2024/6/1 00:04:50
查看原帖
WA on #6
655579
Peizekai楼主2024/5/31 23:46
#include<bits/stdc++.h>
using namespace std;
bool init(int*f,int*g,string a,string b){
    int n=a.size(),m=b.size();
    a=' '+a+' ',b=' '+b+' ';
    bool bl=0;
    for(int i=2;i<=n;i++){
        int j=f[i-1];
        while(j>0&&a[i]!=b[j+1]) j=f[j];
        if(a[i]==b[j+1]) j++;
        f[i]=j;
    }
    for(int i=2;i<=m;i++){
        int j=g[i-1];
        while(j>0&&a[j+1]!=b[i]) j=g[j];
        if(a[j+1]==b[i]) j++;
        g[i]=j;
        if(g[i]==n) bl=1;
    }
    if(a==b) bl=1;
    return bl;
}
const int N=1e5+10;
int ab[N],ba[N],ac[N],ca[N],bc[N],cb[N];
string a,b,c;
int r(string x,string y,string z,int*f,int*g){
    return x.size()+y.size()+z.size()-f[x.size()]-g[y.size()];
}
int main(){
    cin>>a>>b>>c;
    if(a.size()>b.size()) swap(a,b);
    if(b.size()>c.size()) swap(b,c);
    if(a.size()>b.size()) swap(a,b);
    int x=a.size(),y=b.size(),z=c.size();
    if(init(ab,ba,a,b)) ab[x]=ba[y]=ac[x]=ca[z]=x;
    if(init(ac,ca,a,c)) ab[x]=ba[y]=ac[x]=ca[z]=x;
    if(init(bc,cb,b,c)) bc[y]=cb[z]=ab[x]=ba[y]=y;
    int ans=min(
    min(r(a,b,c,ab,bc),
    min(r(a,c,b,ac,cb),r(b,a,c,ba,bc))),
    min(r(b,c,a,bc,ca),
    min(r(c,a,b,ca,ab),r(c,b,a,cb,ba))));
    cout<<ans;
    return 0;
}
2024/5/31 23:46
加载中...