fork(4) download
copy 
  1. /*
  2. written by- Piyush Golani
  3. language- c++
  4. country- India
  5. College- N.I.T Jamshedpur
  6. */
  7. #include <cmath>
  8. #include <ctime>
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12. #include<cstdio>
  13. #include<sstream>
  14. #include<algorithm>
  15. #include<cstdlib>
  16. #include<cstring>
  17. #include<map>
  18. #include<cctype>
  19. using namespace std;
  20. #define pb push_back
  21. #define all(s) s.begin(),s.end()
  22. #define f(i,a,b) for(int i=a;i<b;i++)
  23. #define F(i,a,b) for(int i=a;i>=b;i--)
  24. #define PI 3.1415926535897932384626433832795
  25. #define INF 1000000005
  26. #define BIG_INF 7000000000000000000LL
  27. #define mp make_pair
  28. #define eps 1e-9
  29. #define LL long long
  30. #define si(n) scanf("%d",&n)
  31. #define sll(n) scanf("%lld",&n)
  32. #define mod 1000000007
  33. #define MAX 1005
  34.  
  35. int k,a,b;
  36. int len[MAX][MAX],seg[MAX][MAX];
  37. int solve(char A[],char B[])
  38. {
  39.     f(i,1,a+1)
  40.     {
  41.         f(j,1,b+1)
  42.         {
  43.             seg[i][j]=0;
  44.             len[i][j]=max(len[i][j-1],len[i-1][j]);
  45.             if(A[i-1]==B[j-1])
  46.             {
  47.                 seg[i][j]=seg[i-1][j-1]+1;
  48.                 if(seg[i][j]>=k)
  49.                 {
  50.                     f(p,k,seg[i][j]+1)
  51.                     {
  52.                         len[i][j]=max(len[i][j],len[i-p][j-p]+p);
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.     }
  58.     return len[a][b];
  59. }
  60.  
  61.  
  62.  
  63. int main()
  64. {
  65.     while(1){
  66.     si(k);
  67.     if(k==0) break;
  68.     char A[MAX],B[MAX];
  69.     scanf("%s",A);
  70.     scanf("%s",B);
  71.     a=strlen(A);
  72.     b=strlen(B);
  73.     printf("%d\n",solve(A,B));
  74.     }
  75.     return 0;
  76. }
  77.  
  78.  
Success #stdin #stdout 0.01s 10616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5iJ1qV
language:
C++ (gcc 8.3)
created:
11 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!