tlcs3

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

const char iname[] = "c:\\in.txt";
const char oname[] = "c:\\out.txt";

#define MAXN  1005

#define PB push_back
#define MP make_pair
#define FOR(i, a, b) for (int i = (a); i <= (b); ++ i)
#define MAX(a, b)    ((a) > (b) ? (a) : (b))

char A[MAXN], B[MAXN], RA[MAXN], RB[MAXN];

int L1[MAXN], L2[MAXN], K[2][MAXN];


void lcs(int m, int n, char *A, char *B, int L[])
{
    FOR (j, 0, n)  K[1][j] = 0;
    FOR (i, 1, m) {
        FOR (j, 0, n)  K[0][j] = K[1][j];
        FOR (j, 1, n) {
            if (A[i] == B[j])
                K[1][j] = K[0][j - 1] + 1;
            else
                K[1][j] = MAX(K[0][j], K[1][j - 1]);
        }
    }
    FOR (j, 0, n)  L[j] = K[1][j];
}

void work(int m, int n, char *A, char *B, char *RA, char *RB, vector <int> &C)
{
    if (n == 0) /* add the empty string to C */
        return ;
    if (m == 1) {
        FOR (j, 1, n) if (A[1] == B[j]) {
            C.PB(A+1 - ::A);
            break ;
        }
        return ;
    }

    int i = (m+1) / 2;
    lcs(i, n, A, B, L1);
    lcs(m - i, n, RA, RB, L2);

    int M = 0;
    FOR (j, 0, n)
        M = MAX(M, L1[j] + L2[n - j]);
    int k;
    FOR (j, 0, n) if (M == L1[j] + L2[n - j]) {
        k = j;
        break ;
    }

    work(i, k, A, B, RA + m-i, RB + n-k, C);
    work(m - i, n - k, A + i, B + k, RA, RB, C);
}

int main(void)
{
    clock_t tstart = clock();

    int css;
    int m, n;
    vector <int> R;

    scanf("%d", &css);
    FOR (stp, 1, css)
    {
        scanf("%d %s\n", &m, A+1);
        FOR (i, 1, m)
            RA[i] = A[m-i+1];
        scanf("%d %s\n", &n, B+1);
        FOR (i, 1, n)
            RB[i] = B[n-i+1];

        if (((double)(clock() - tstart)) / CLOCKS_PER_SEC < 4.95)
        {
            vector <int>().swap(R);
            work(m, n, A, B, RA, RB, R);

            if (R.size()) {
                printf("case %d Y\n", stp);
                printf("%d\n", R.size());
                int j = 0;
                FOR (i, 0, (int)R.size() - 1) {
                    while (B[++ j] != A[R[i]]) ;
                    printf("%c %d %d\n", B[j], R[i], j);
                }
            } else
                printf("case %d N\n", stp);
        } else
            printf("case %d N\n", stp);
    }

    return 0;
}