1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| #include <bits/stdc++.h> #define Base 131 #define MAXN 200005 #define LL long long #define ll long long #define mem(a) memset(a,0,sizeof(a)) #define memmax(a) memset(a,0x3f,sizeof(a)) #define ull unsigned long long using namespace std; ull p[MAXN];; ull h1[MAXN],h2[MAXN]; inline void Init_Hash(string A,ull *h){ h[0]=(A[0]-'a'); for (register int i=1;i<(int)A.size();++i){ h[i]=h[i-1]*Base+(ull)(A[i]-'a'); } } inline ull Hash(int l,int r,ull *h){ if (l==0) return h[r]; return h[r]-h[l-1]*p[r-l+1]; } inline string connect(string A,string B){ Init_Hash(A,h1),Init_Hash(B,h2); if (B.size()<=A.size()){ ull HashB=Hash(0,B.size()-1,h2); for (register int i=0;i<(int)A.size()-(int)B.size()+1;++i){ if (Hash(i,i+(int)B.size()-1,h1)==HashB){ return A; } } } int Size=min(A.size(),B.size()); for (register int i=Size-1;i>=1;--i){ if (Hash((int)A.size()-i,(int)A.size()-1,h1)==Hash(0,i-1,h2)){ string ans=A; for (register int j=i;j<(int)B.size();++j){ ans+=B[j]; } return ans; } } return A+B; } inline void Init_P(){ p[0]=1; for (register int i=1;i<MAXN;++i){ p[i]=p[i-1]*Base; } } int main(){ Init_P(); string s1,s2,s3; cin>>s1>>s2>>s3; int ans=0x7fffffff; ans=min(ans,(int)connect(s1,connect(s2,s3)).size()); ans=min(ans,(int)connect(s1,connect(s3,s2)).size()); ans=min(ans,(int)connect(s2,connect(s1,s3)).size()); ans=min(ans,(int)connect(s2,connect(s3,s1)).size()); ans=min(ans,(int)connect(s3,connect(s1,s2)).size()); ans=min(ans,(int)connect(s3,connect(s2,s1)).size()); ans=min(ans,(int)connect(connect(s2,s3),s1).size()); ans=min(ans,(int)connect(connect(s3,s2),s1).size()); ans=min(ans,(int)connect(connect(s1,s3),s2).size()); ans=min(ans,(int)connect(connect(s3,s1),s2).size()); ans=min(ans,(int)connect(connect(s1,s2),s3).size()); ans=min(ans,(int)connect(connect(s2,s1),s3).size()); printf("%d\n",ans); }
|