fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int mod1=1e9+7,mod2=998244353,N=5e4+5;
  5. signed main()
  6. {
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(0);
  9.     cout.tie(0);
  10.     int n;
  11.     cin>>n;
  12.     string s[n];
  13.     for(int a=0;a<n;a++){
  14.         cin>>s[a];
  15.     }
  16.     int mn=1e9;
  17.     string S;
  18.     for(int a=0;a<n;a++){
  19.         if(s[a].size()<mn){
  20.             S=s[a];
  21.             mn=s[a].size();
  22.         }
  23.     }
  24.     bool check=0;
  25.     int ans=min((int)60,(int)S.size());
  26.     while(!check){
  27.         for(int i=0;i<=S.size()-ans;i++){
  28.             string B=S.substr(i,ans);
  29.             bool ch[n];
  30.             for(int b=0;b<n;b++){
  31.                 if(s[b]!=S){
  32.                     string A=s[b];
  33.                     bool K[A.size()+1];
  34.                     int dp[A.size()+1];
  35.                     dp[0]=0;
  36.                     for(int a=1;a<=A.size();a++){
  37.                         dp[a]=(dp[a-1]*26+A[a-1]-94+mod1)%mod1;
  38.                     }
  39.                     int dp1[B.size()+1];
  40.                     dp1[0]=0;
  41.                     int sum=1;
  42.                     for(int a=0;a<B.size();a++){
  43.                         sum*=26;
  44.                         sum%=mod1;
  45.                     }
  46.                     for(int a=1;a<=B.size();a++){
  47.                         dp1[a]=(dp1[a-1]*26+B[a-1]-94+mod1)%mod1;
  48.                     }
  49.                     int m=0;
  50.                     for(int a=B.size();a<=A.size();a++){
  51.                         if((dp[a]%mod1-(dp[a-B.size()]*sum)%mod1+mod1)%mod1==dp1[B.size()]) K[a-B.size()+1]=1;
  52.                     }
  53.                     dp[0]=0;
  54.                     for(int a=1;a<=A.size();a++){
  55.                         dp[a]=(dp[a-1]*26+A[a-1]-94+mod2)%mod2;
  56.                     }
  57.                     dp1[0]=0;
  58.                     sum=1;
  59.                     for(int a=0;a<B.size();a++){
  60.                         sum*=26;
  61.                         sum%=mod2;
  62.                     }
  63.                     for(int a=1;a<=B.size();a++){
  64.                         dp1[a]=(dp1[a-1]*26+B[a-1]-94+mod2)%mod2;
  65.                     }
  66.                     for(int a=B.size();a<=A.size();a++){
  67.                         if((dp[a]%mod2-(dp[a-B.size()]*sum)%mod2+mod2)%mod2==dp1[B.size()]){
  68.                             if(K[a-B.size()+1]){
  69.                                 ch[b]=1;
  70.                                 break;
  71.                             }
  72.                         }
  73.                     }
  74.                 }
  75.                 else ch[b]=1;
  76.             }
  77.             bool ss=0;
  78.             for(int a=0;a<n;a++){
  79.                 if(!ch[a]) ss=1;
  80.             }
  81.             if(!ss){
  82.                 check=1;
  83.                 break;
  84.             }
  85.         }
  86.         if(check) break;
  87.         else ans--;
  88.     }
  89.     cout<<ans;
  90. }
  91.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
2
aaaba
bbaaa
stdout
copy 
3
https://ideone.com/Vp4AEx
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!