MSTRING - String problem

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 1010;
using namespace std;

struct STR {
    char str[N];
    int next[N][26];
    int n;
    void Init() {
        n = strlen(str + 1);
        for(int j = 0; j < 26; j++) next[n][j] = 0;
        for(int i = n - 1; i >= 0; i--) 
            for(int j = 0; j < 26; j++)
                if (str[i + 1] - 'a' == j)
                    next[i][j] = i + 1;
                else
                    next[i][j] = next[i + 1][j];
    }
} a, b;
int res;
int d[N][N];
ii Q[N * N];

void BFS() {
    int l = 1, r = 1;
    Q[1] = ii(0, 0);
    while (l <= r) {
        ii u = Q[l++];
        for(int j = 0; j < 26; j++) {
            int x = a.next[u.X][j];
            int y = b.next[u.Y][j];
            if (x == 0) continue;
            if (y == 0) {res = d[u.X][u.Y] + 1; return;}
            if (d[x][y] > 0) continue;
            d[x][y] = d[u.X][u.Y] + 1;
            Q[++r] = ii(x, y);
        }
    }
}

int main() {
    scanf("%s\n", a.str + 1); scanf("%s", b.str + 1);
    a.Init(); b.Init();
    BFS();
    printf("%d", res);
    return 0;
}

Download