fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int solve(string s,string t)
  5. {
  6.   s = t  + '#' + s ;
  7.   int n = t.length();
  8.   int m = s.length();
  9.  
  10.   int pi[m+1] = {0};
  11.   for(int i=1;i<m;i++)
  12.   {
  13.   	int l = pi[i-1];
  14.   	while(l>0 && s[i]!=s[l]) l = pi[l-1];
  15.   	if(s[i]==s[l]) l++;
  16.   	pi[i] = l;
  17.   }
  18.  
  19.   int ans = 0,res = 0;
  20.   for(int i=n+1;i<m;i++)
  21. 	 if(pi[i]>ans){ res = pi[i]; ans = i - pi[i] - n; }
  22.   return ans;
  23. }
  24.  
  25. int main()
  26. {
  27.    ios_base::sync_with_stdio(false); cin.tie(0);
  28.    cout.tie(0);
  29.    string a,b;	
  30.    int n;
  31.    cin>>n>>a>>b;
  32.    b = b  + b;
  33.    cout<<solve(b,a)<<'\n';
  34. }
Success #stdin #stdout 0s 4512KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Ga08HP
language:
C++14 (gcc 8.3)
created:
4 years 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!