1015 Letter-moving Game
Statement
Metadata
- 作者: CAO, Peng
- 单位: Google
- 代码长度限制: 16 KB
- 时间限制: 200 ms
- 内存限制: 64 MB
Here is a simple intersting letter-moving game. The game starts with 2 strings S and T consist of lower case English letters. S and T contain the same letters but the orders might be different. In other words S can be obtained by shuffling letters in String T. At each step, you can move one arbitrary letter in S either to the beginning or to the end of it. How many steps at least to change S into T?
Input Specification
Each input file contains one test case. For each case, the first line contains the string S, and the second line contains the string T. They consist of only the lower case English letters and S can be obtained by shuffling T's letters. The length of S is no larger than 1000.
Output Specification
For each case, print in a line the least number of steps to change S into T in the game.
Sample Input
Sample Output
Sample Solution
(0) starts from iononmrogdg
(1) Move the last g to the beginning: giononmrogd
(2) Move m to the end: giononrogdm
(3) Move the first o to the end: ginonrogdmo
(4) Move r to the end: ginonogdmor
(5) Move the first n to the end: gionogdmorn
(6) Move i to the end: gonogdmorni
(7) Move the first n to the end: googdmornin
(8) Move the second g to the end: goodmorning
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, ALP = 26;
char s[N], t[N];
int n, f[N][ALP], nx[ALP];
int main() {
while (scanf("%s%s", s + 1, t + 1) != EOF) {
n = strlen(s + 1);
for (int i = 0; i < ALP; ++i) nx[i] = n + 1;
for (int i = n; i >= 0; --i) {
int ch = s[i] - 'a';
for (int j = 0; j < ALP; ++j) {
f[i][j] = nx[j];
}
if (i)
nx[ch] = i;
}
int res = 0;
for (int i = 1, j; i <= n; ++i) {
int p = 0;
for (j = i; j <= n; ++j) {
int ch = t[j] - 'a';
if (f[p][ch] > n)
break;
p = f[p][ch];
}
res = max(res, j - i);
}
printf("%d\n", n - res);
}
return 0;
}