题解

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> buildFail(const string& pattern) {
int m = pattern.size();
vector<int> fail(m, 0);
for (int i = 1, j = 0; i < m; i) {
while (j > 0 && pattern[i] != pattern[j]) {
j = fail[j - 1];
}
if (pattern[i] == pattern[j]) {
j;
}
fail[i] = j;
}
return fail;
}

int main() {
string s, pattern;
cin >> s >> pattern;
int n = s.size();
int m = pattern.size();
if (m == 0) {
cout << 0 << endl;
return 0;
}
vector<int> fail = buildFail(pattern);
vector<vector<int>> dp(n + 1, vector<int>(m, n + 1));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; j) {
if (dp[i][j] == n + 1) continue;
// 移除当前字符
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
// 保留当前字符
int k = j;
while (k > 0 && s[i] != pattern[k]) {
k = fail[k - 1];
}
if (s[i] == pattern[k]) {
k;
}
if (k < m) {
dp[i + 1][k] = min(dp[i + 1][k], dp[i][j]);
}
}
}
cout << *min_element(dp[n].begin(), dp[n].end()) << endl;
return 0;
}