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;
}