fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define mod 1000000007
  4. using namespace std;
  5. int h1[1011],h2[1011],has[1011],n,m,dp[1011][1011],k;
  6. string s,ss ;
  7. int bigmod(int a , int b)
  8. {
  9.     if(b == 0) return 1%mod ;
  10.     int x = bigmod(a,b/2) ;
  11.     x = ((x%mod)*(x%mod))%mod ;
  12.     if(b%2) x = ((x%mod)*(a%mod))%mod ;
  13.     return x ;
  14. }
  15. int fun(int i1 , int i2)
  16. {
  17.     if(i1==n || i2==m) return 0 ;
  18.     if(dp[i1][i2]!=-1) return dp[i1][i2] ;
  19.     int fl=0,ct=0 ;
  20.     if(s[i1]==ss[i2])
  21.     {
  22.         int lo=1,hi=min(n-i1,m-i2) ; ct=1 ;
  23.         int md=(lo+hi)/2 ;
  24.         while(lo<=hi)
  25.         {
  26.             int x,y ;
  27.             int md=(lo+hi)/2 ;
  28.             if(i1==0) x=h1[i1+md-1] ;
  29.             else x=((h1[i1+md-1]-h1[i1-1]+mod)%mod)*has[i1] ; x%=mod ;
  30.             if(i2==0) y=h2[i2+md-1] ;
  31.             else y=((h2[i2+md-1]-h2[i2-1]+mod)%mod)*has[i2] ; y%=mod ;
  32.            // cout<<lo<<" "<<hi<<" "<<md<<" "<<x<<" "<<y<<endl ;
  33.             if(x==y) {ct=md ; lo=md+1 ; }
  34.             else hi=md-1 ;
  35.         }
  36.         if(ct>=k) fl=1 ;
  37.     }
  38.     int as=0 ;
  39.     if(ct>=k) as=ct+fun(i1+ct,i2+ct) ;
  40.     int x=fun(i1+1,i2) , y=fun(i1,i2+1) ;
  41.     return dp[i1][i2]=max(max(x,y),as) ;
  42. }
  43. int32_t main()
  44. {
  45.     int iv=bigmod(53,mod-2) ;//cout<<iv<<endl ;
  46.     has[0]=1 ;
  47.     for(int i = 1 ; i <= 1008 ; i++) has[i]=(has[i-1]*iv)%mod ;
  48.     //for(int i = 0 ; i < 6 ; i++) cout<<has[i]<<" " ; cout<<endl ;
  49.     while(cin>>k,k)
  50.     {
  51.         cin>>s>>ss ; n=s.size() ; m=ss.size() ;
  52.         for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < m ; j++) dp[i][j]=-1 ;
  53.         for(int i = 0 ; i < n ; i++) h1[i]=0 ;
  54.         for(int i = 0 ; i < m ; i++) h2[i]=0 ;
  55.         int vl=1 ;
  56.         for(int i = 0 ; i < n ; i++)
  57.         {
  58.             int x=s[i]-'a'+1 ;
  59.             h1[i]=(x*vl%mod)%mod ; vl*=53 ; vl%=mod ;
  60.             if(i!=0) h1[i]+=h1[i-1] ;
  61.         }
  62.         vl=1 ;
  63.         for(int i = 0 ; i < m ; i++)
  64.         {
  65.             int x=ss[i]-'a'+1 ;
  66.             h2[i]=(x*vl%mod)%mod ; vl*=53 ; vl%=mod ;
  67.             if(i!=0) h2[i]+=h2[i-1] ;
  68.         }
  69.         //for(int i = 0 ; i < n ; i++) cout<<h1[i]<<" " ; cout<<endl ;
  70.         //for(int i = 0 ; i < m ; i++) cout<<h2[i]<<" " ; cout<<endl ;
  71.         int mx=fun(0,0) ;
  72.         cout<<mx<<endl ;
  73.     }
  74. }
  75.  
Success #stdin #stdout 0s 4728KB
comments (?)
stdin
copy 
3
lovxxelyxxxxx
xxxxxxxlovely
1
lovxxelyxxxxx
xxxxxxxlovely
3
lovxxxelxyxxxx
xxxlovelyxxxxxxx
4
lovxxxelyxxx
xxxxxxlovely
3
baaaa
baaa
4
aggasdfa
aggajasdfa
2
aab
aaab
2
aabc
aadbc
5
cabcdeabcdefg
cabcdefg
2
abc
abbc
3
pqrz
pqrpqrz
4
aggasdfa
aggakasdfa
0
stdout
copy 
6
7
10
0
4
8
3
4
7
2
4
8
https://ideone.com/Qwe7dU
language:
C++14 (gcc 8.3)
created:
3 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!