fork download
copy 
  1. //#include<time.h>
  2. #include<bits/stdc++.h>
  3. #define fi(i, a, b) for(int i = a; i < b ; ++i)
  4. #define fd(i, a, b) for(int i = a; i > b ; --i)
  5. #define all(c) c.begin(), c.end()
  6. #define llu long long
  7.  
  8. using namespace::std;
  9. char a[1001],b[1001];
  10. int lcs[1001][1001];
  11. int aid[1001];
  12. int bid[1001];
  13. //void print(char i)
  14. //{
  15. //    cout<<i;
  16. //}
  17. int main()
  18. {
  19.     int t, n, m, T = 0, q = 0;
  20. //    clock_t c;
  21. //    c = clock();
  22. //    freopen("in.txt", "r", stdin);
  23.    scanf("%d", &t);
  24.     while(++T <=t )
  25.     {
  26.         scanf("%d %s", &n, a);
  27.         scanf("%d %s", &m, b);
  28. /**        cout<<"\na using for_each : \t";
  29.         for_each(a.begin(), a.end(), print);
  30.         cout<<"\na using for : \t";
  31.         fi(i, 1, n+1)
  32.         cout<<a.at(i-1);        **/
  33.  
  34.     fi(i, 0, n)
  35.     {fi(j, 0, m)
  36.     if(a[i] == b[j]) lcs[i+1][j+1] = lcs[i][j] +1;
  37.     else  lcs[i+1][j+1] = max(lcs[i+1][j], lcs[i][j+1]);
  38.     }
  39.  
  40. int nn = n;
  41. int mm = m;
  42. q = 0;
  43.     while(n>0 && m>0)
  44.     {
  45.         if(a[n-1] == b[m-1])
  46.             {
  47.                 aid[q] = n;
  48.                 bid[q++] = m;
  49.                 n--;
  50.                 m--;
  51.             }
  52.         else if(lcs[n-1][m] > lcs[n][m-1])
  53.         n--;
  54.         else m--;
  55.     }
  56.     if(lcs[nn][mm] > 1)
  57.     {
  58.         printf("case  %d Y\n", T);
  59.         printf("%d\n", lcs[nn][mm]);
  60.         for(int i = q-1; i >=0; --i)
  61.             printf("%c %d %d\n",a[aid[i]-1],  aid[i], bid[i]);
  62.     }
  63.     else printf("case %d N\n", T);
  64. //    fi(i, 1, nn+1)
  65. //    {
  66. //        fi(j, 1, mm+1)
  67. //    cout<<lcs[i][j]<<' ';
  68. //    cout<<endl;
  69. //    }
  70. //    cout<<"\n**************************************************888**************************\n";
  71.     }
  72. //    cout<<t<<"clicks"<<" "<<((float)t)/CLOCKS_PER_SEC<<"seconds";
  73.  
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 7224KB
comments (?)
stdin
copy 
4
5 ddacc
3 cac
7 cbbccbc
4 aaca
4 cbeb
5 fdceb
8 computer
7 chapter
stdout
copy 
case  1 Y
2
c 4 1
c 5 3
case 2 N
case  3 Y
3
c 1 3
e 3 4
b 4 5
case  4 Y
5
c 1 1
p 4 4
t 6 5
e 7 6
r 8 7
https://ideone.com/MijXTp
language:
C++14 (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!