Cod sursa(job #596564)

Utilizator SpiderManSimoiu Robert SpiderMan Data 17 iunie 2011 19:10:29
Problema Seif Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
# include <cstdio>
# include <cstring>

const char *FIN = "seif.in", *FOU = "seif.out";
const int MAX = 1005;

char S[2][MAX];
int dp[2][MAX][26], lun[2], T, K;
short best[MAX][MAX];

inline int max (int a, int b) {
    return (a > b ? a : b);
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    for (scanf ("%d", &T); T; --T, printf ("\n")) {
        scanf ("%d %s %s", &K, S + 0, S + 1);
        for (int i = 0; i < 2; ++i)
            lun[i] = strlen (S[i]);
        memset (dp, -1, sizeof (dp));
        for (int i = 0; i < 2; ++i) {
            for (int j = lun[i] - 1; j >= 0; --j) {
                for (int k = 0; k < 26; ++k)
                    dp[i][j][k] = dp[i][j + 1][k];
                dp[i][j][S[i][j] - 'A'] = j;
            }
        }
        memset (best, 0, sizeof (best));
        for (int i = lun[0] - 1; i >= 0; --i) {
            for (int j = lun[1] - 1; j >= 0; --j) {
                best[i][j] = (S[0][i] == S[1][j] ? best[i + 1][j + 1] + 1 : max (best[i + 1][j], best[i][j + 1]));
            }
        }
        for (int A[] = {-1, -1}, stop = 1; stop; ) {
             stop = 0;
             for (int i = 25; i >= 0 && stop == 0; --i) {
                 int B[] = {0, 0};
                 for (int j = 0; j < 2; ++j)
                     B[j] = dp[j][A[j] + 1][i];
                 if (B[0] == -1 || B[1] == -1) continue;
                 if (best[B[0]][B[1]] >= K) {
                     printf ("%c", i + 'A');
                     memcpy (A, B, sizeof (B));
                     stop = 1, --K;
                 }
             }
        }
    }
}