SHARE
TWEET

Untitled

a guest Aug 19th, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define MAX             100005
  6. #define MOD             1000003
  7. #define eps             1e-6
  8. int fx[] =              {1,-1,0,0};
  9. int fy[] =              {0,0,1,-1};
  10.  
  11. #define FastRead        ios_base::sync_with_stdio(0);cin.tie(0);
  12. #define fRead           freopen("in.txt","r",stdin);
  13. #define fWrite          freopen ("in.txt","w",stdout);
  14.  
  15. #define ll              long long
  16. #define ull             unsigned long long
  17. #define ff              first
  18. #define ss              second
  19. #define pb              push_back
  20. #define PI              acos(-1.0)
  21. #define mk              make_pair
  22. #define pii             pair<int,int>
  23. #define pll             pair<LL,LL>
  24. #define vi              vector <int>
  25. #define vl              vector <LL>
  26. #define vp              vector<pii>
  27. #define all(a)          a.begin(),a.end()
  28.  
  29. #define min3(a,b,c)     min(a,min(b,c))
  30. #define max3(a,b,c)     max(a,max(b,c))
  31. #define min4(a,b,c,d)   min(a,min(b,min(c,d)))
  32. #define max4(a,b,c,d)   max(a,max(b,max(c,d)))
  33.  
  34. #define FOR(i,a,b)      for(int i=a;i<=b;i++)
  35. #define ROF(i,a,b)      for(int i=a;i>=b;i--)
  36. #define REP(i,b)        for(int i=0;i<b;i++)
  37. #define IT(it,x)    for(it=x.begin();it!=x.end;it++)
  38.  
  39. #define MEM(a,x)        memset(a,x,sizeof(a))
  40. #define ABS(x)          ((x)<0?-(x):(x))
  41. #define SORT(v)         sort(v.begin(),v.end())
  42. #define REV(v)          reverse(v.begin(),v.end())
  43.  
  44. //#define NUM 1000005bool flag[NUM];vector <int> prime;inline void sieve(){flag[1]=true;for(int i=4; i<NUM; i+=2){flag[i]=true;}for(int i=3; i*i<=NUM; i+=2){if(!flag[i]){for(int j=i*i; j<NUM; j+=2*i){flag[j]=true;}}}prime.pb(2);for(int i=3; i<NUM; i+=2){if(!flag[i]){prime.pb(i);}}return;}
  45.  
  46. //inline int NOD(ll n){int div=1;for(int i=0; prime[i]*prime[i]<=n; i++){if(n%prime[i]==0){int cnt=0;while(n%prime[i]==0){n/=prime[i];cnt++;}div*=(cnt+1);}}if(n>1){div*=2;}return div;}
  47.  
  48. //inline ll BigMod(ll B,ll P,ll M){ll R=1;while(P>0){if(P & 1) R=(R*B)%M;P/=2;B=(B*B)%M;}return R%M;}
  49.  
  50. //inline void build(int L,int R,int pos){if(L==R){tree[pos]=arr[L];return;}int mid=(L+R)/2;build(L,mid,pos*2+1);build(mid+1,R,pos*2+2);tree[pos]=min(tree[pos*2+1],tree[pos*2+2]);return;}
  51.  
  52. //inline int query(int ql,int qr,int L,int R,int pos){if(ql>R or qr<L) return MAX;else if(ql<=L and qr>=R) return tree[pos];int mid=(L+R)/2;int p=query(ql,qr,L,mid,2*pos+1);int q=query(ql,qr,mid+1,R,2*pos+2);return min(p,q);}
  53.  
  54. //void updateRange(int b,int e,int L,int R,int pos,ll val){if(lazy[pos]!=0){tree[pos]+=(R-L+1)*lazy[pos];if(L!=R){lazy[2*pos+1]+=lazy[pos];lazy[2*pos+2]+=lazy[pos];}lazy[pos]=0;}if(L>R or L>e or R<b) return;if(L>=b and R<=e){tree[pos]+=(R-L+1)*val;if(L!=R){lazy[2*pos+1]+=val;lazy[2*pos+2]+=val;}return;}int mid=(L+R)/2;updateRange(b,e,L,mid,2*pos+1,val);updateRange(b,e,mid+1,R,2*pos+2,val);tree[pos]=tree[2*pos+1]+tree[2*pos+2];return;}
  55.  
  56. //ll getSum(int ql,int qr,int L,int R,int pos){if(lazy[pos]!=0){tree[pos]+=(R-L+1)*lazy[pos];if(L!=R){lazy[2*pos+1]+=lazy[pos];lazy[2*pos+2]+=lazy[pos];}lazy[pos]=0;}if(L>R or ql>R or qr<L) return 0;if(L>=ql and qr>=R) return tree[pos];int mid=(L+R)/2;return getSum(ql,qr,L,mid,2*pos+1)+getSum(ql,qr,mid+1,R,2*pos+2);}
  57.  
  58. //inline void bfs(int s){MEM(vis,0);vis[s]=1;queue<int>Q;Q.push(s);while(!Q.empty()){int x=Q.front();Q.pop();REP(i,V[x].size()){if(!vis[V[x][i]]){vis[V[x][i]]=1;Q.push(V[x][i]);}}}return;}
  59.  
  60. //int cell[100][100]; int d[100][100],vis[100][100];int row,col;inline void bfs(int sx,int sy){ MEM(vis,0);vis[sx][sy]=1;queue<pii>q; q.push(pii(sx,sy));while(!q.empty()){pii top=q.front();q.pop();for(int k=0; k<4; k++){int tx=top.ff+fx[k];int ty=top.ss+fy[k]; if(tx>=0 and tx<row and ty>=0 and ty<col and cell[tx][ty]!=-1 and vis[tx][ty]==0){vis[tx][ty]=1;d[tx][ty]=d[top.ff][top.ss]+1;q.push(pii(tx,ty)); }}}return;}
  61.  
  62. //inline void bi_dfs(int s,int c){if(vis[s]) return;vis[s]=1;color[s]=c;REP(i,V[s].size()) dfs(V[s][i],1-c);return;}
  63.  
  64. //struct point{int name,val;bool operator <(const point &p) const{return p.val < val;}};vector<int>V[105];int dis[105],cost[105][105];priority_queue<point>Q;void Dijkstra(int s){dis[s]=0;point get;get.name=s;get.val=0;Q.push(get);while(!Q.empty()){point tmp=Q.top();Q.pop();int now=tmp.name;REP(i,V[now].size()){int x=V[now][i];if(dis[now]+cost[now][x]<dis[x]){dis[x]=dis[now]+cost[now][x];get.name=x;get.val=dis[x];Q.push(get);}}}return;}
  65.  
  66. //struct edge{int u,v,w;bool operator < (const edge &p) const{return w < p.w;}};int pr[MAX];vector<edge>e;int find(int r){return pr[r]= (pr[r]==r) ? r:find(pr[r]);}int kruskal(int n){sort(e.begin(),e.end());FOR(i,1,n) pr[i]=i;int cnt=0,sum=0;REP(i,e.size()){int x=find(e[i].u);int y=find(e[i].v);if(x!=y){pr[x]=y;cnt++;sum+=e[i].w;if(cnt==n-1) break;}}return sum;}
  67.  
  68. //inline ll GCD (ll a,ll b ) {if(a < b) swap(a, b); while ( b ) { a = a % b; swap ( a, b ); } return a;}
  69.  
  70. //int Set(int N,int pos){return N=N | (1<<pos);}
  71.  
  72. //int reset(int N,int pos){return N= N & ~(1<<pos);}
  73.  
  74. //bool check(int N,int pos){return (bool)(N & (1<<pos));}
  75.  
  76. //// ***************************************************** TEMPLATE ***************************************************** ////
  77.  
  78. int flag[1000020];
  79.  
  80. int freq[20];
  81.  
  82.  
  83.  
  84. struct SuffixArray {
  85.     string a;
  86.     int N, m;
  87.     vector<int> SA, LCP, x, y, w, c;
  88.  
  89.     SuffixArray(string _a, int m = 256) : a(" " + _a), N(a.length()), m(m),
  90.             SA(N), LCP(N), x(N), y(N), w(max(m, N)), c(N) {
  91.         a[0] = 0;
  92.         DA();
  93.         kasaiLCP();
  94.         #define REF(X) { rotate(X.begin(), X.begin()+1, X.end()); X.pop_back(); }
  95.         REF(SA); REF(LCP);
  96.         a = a.substr(1, a.size());
  97.         for(int i = 0; i < (int) SA.size(); ++i) --SA[i];
  98.         #undef REF
  99.     }
  100.  
  101.     inline bool cmp (const int a, const int b, const int l) { return (y[a] == y[b] && y[a + l] == y[b + l]); }
  102.  
  103.     void Sort() {
  104.         for(int i = 0; i < m; ++i) w[i] = 0;
  105.         for(int i = 0; i < N; ++i) ++w[x[y[i]]];
  106.         for(int i = 0; i < m - 1; ++i) w[i + 1] += w[i];
  107.         for(int i = N - 1; i >= 0; --i) SA[--w[x[y[i]]]] = y[i];
  108.     }
  109.  
  110.     void DA() {
  111.         for(int i = 0; i < N; ++i) x[i] = a[i], y[i] = i;
  112.         Sort();
  113.         for(int i, j = 1, p = 1; p < N; j <<= 1, m = p) {
  114.             for(p = 0, i = N - j; i < N; i++) y[p++] = i;
  115.             for (int k = 0; k < N; ++k) if (SA[k] >= j) y[p++] = SA[k] - j;
  116.             Sort();
  117.             for(swap(x, y), p = 1, x[SA[0]] = 0, i = 1; i < N; ++i)
  118.                 x[SA[i]] = cmp(SA[i - 1], SA[i], j) ? p - 1 : p++;
  119.         }
  120.     }
  121.  
  122.     void kasaiLCP() {
  123.         for (int i = 0; i < N; i++) c[SA[i]] = i;
  124.         for (int i = 0, j, k = 0; i < N; LCP[c[i++]] = k)
  125.             if (c[i] > 0) for (k ? k-- : 0, j = SA[c[i] - 1]; a[i + k] == a[j + k]; k++);
  126.             else k = 0;
  127.     }
  128. };
  129.  
  130.  
  131.  
  132.  
  133.  
  134. int main()
  135. {
  136.  
  137.     //fRead
  138.  
  139.     FastRead
  140.  
  141.     int k=0;
  142.     string str="";
  143.     string s;
  144.  
  145.     char ch='&';
  146.  
  147.     int cur=0;
  148.  
  149.     //int t=2;
  150.     while(cin >> s)
  151.     {
  152.         //cin >> s;
  153.         k++;
  154.         int x=s.size();
  155.         FOR(i,cur,cur+x)flag[i]=k;
  156.         cur+=x;
  157.         cur++;
  158.         str+=s;
  159.         str+=ch;
  160.         ch++;
  161.     }
  162.  
  163. //    cout << str << '\n';
  164. //
  165. //    REP(i,str.size())cout << flag[i] << ' ';
  166. //    cout << '\n';
  167.  
  168.     SuffixArray sa(str,256);
  169.  
  170.     int n=str.size();
  171.  
  172. //    FOR(i,k,n-1)cout << sa.SA[i] << ' ';
  173. //    cout << '\n';
  174. //    FOR(i,k,n-1)cout << flag[sa.SA[i]] << ' ';
  175. //    cout << '\n';
  176. //    FOR(i,k,n-1)cout << sa.LCP[i] << ' ';
  177. //    cout << '\n';
  178.  
  179.     deque <int> dq;
  180.  
  181.     //deque <int> :: iterator it;
  182.  
  183.  
  184.  
  185.     int cnt=1;
  186.     int st=k,en=k;
  187.     freq[flag[sa.SA[k]]]++;
  188.  
  189.     int ans=0;
  190.  
  191.     while(en<n)
  192.     {
  193.         if(st>en)break;
  194.  
  195.         if(cnt==k)
  196.         {
  197.             //cout << "********\n";
  198.             int d=sa.SA[st];
  199.             st++;
  200.             //cout << st << ' ' << sa.SA[st] << ' ' << sa.LCP[st] << " **\n";
  201.             int x=sa.LCP[st];
  202.             d=flag[d];
  203.             freq[d]--;
  204.             if(freq[d]==0)cnt--;
  205. //            for(it=dq.begin();it!=dq.end();it++)cout << *it << ' ';
  206. //            cout << '\n';
  207.             if(dq.front()==x)dq.pop_front();
  208. //            for(it=dq.begin();it!=dq.end();it++)cout << *it << ' ';
  209. //            cout << '\n';
  210.             if(cnt==k and en<n)
  211.             {
  212.                 //cout << "$$$$$$\n";
  213.                 int a=dq.front();
  214.                 //cout << a << '\n';
  215.                 ans=max(ans,a);
  216.                 //cout << ans << '\n';
  217.                 //cout << "$$$$$$\n";
  218.             }
  219.             //cout << "********\n";
  220.         }
  221.  
  222.         if(cnt!=k)
  223.         {
  224.             //cout << "^^^^^^^^\n";
  225.             en++;
  226.             //cout << en << ' ' << sa.SA[en] << ' ' << sa.LCP[en] << " **\n";
  227.             int x=sa.LCP[en];
  228.             int d=sa.SA[en];
  229.             d=flag[d];
  230.             freq[d]++;
  231.             if(freq[d]==1)cnt++;
  232. //            for(it=dq.begin();it!=dq.end();it++)cout << *it << ' ';
  233. //            cout << '\n';
  234.             while(dq.size() and dq.back()>x)dq.pop_back();
  235.             dq.push_back(x);
  236. //            for(it=dq.begin();it!=dq.end();it++)cout << *it << ' ';
  237. //            cout << '\n';
  238.             if(cnt==k and en<n)
  239.             {
  240.                 //cout << "!!!!!!!!!\n";
  241.                 int a=dq.front();
  242.                 //cout << a << '\n';
  243.                 ans=max(ans,a);
  244.                 //cout << ans << '\n';
  245.                 //cout << "!!!!!!!!!\n";
  246.             }
  247.             //cout << "^^^^^^^^\n";
  248.         }
  249.     }
  250.  
  251.     cout << ans;
  252.  
  253. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top