第4个子任务中,为什么只转移最近的一个位置,自己YY吧(多YY有益身体健康).
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class T>inline void read(T &num) {
register char ch; register int flg = 1;
while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;
for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar());
num *= flg;
}
const int MAXN = 2005;
const int C = 26;
char A[MAXN], B[MAXN];
int f[MAXN][MAXN];
namespace task1 {
inline void solve() {
int ans = MAXN-1;
for(int i = 1; A[i]; ++i) {//字串的右端点
int mx = 0;
for(int j = 1; B[j]; ++j)
if(A[i] == B[j])
mx = max(mx, f[i][j] = f[i-1][j-1] + 1);
if(mx < i) ans = min(ans, mx+1);
}
printf("%d
", (A[ans] && B[ans]) ? ans : -1);
}
}
namespace task2 {
inline void solve() {
int ans = MAXN-1;
for(int i = 1; A[i]; ++i) {//字串的右端点
int mx = 0;
for(int j = 1; B[j]; ++j) {
if(A[i] == B[j])
mx = max(mx, f[i][j] = f[i-1][j-1] + 1);
else mx = max(mx, f[i][j] = f[i][j-1]);
}
if(mx < i) ans = min(ans, mx+1);
}
printf("%d
", (A[ans] && B[ans]) ? ans : -1);
}
}
namespace task3 {
int sz, last, len[MAXN<<1], link[MAXN<<1], ch[MAXN<<1][C], dp[MAXN<<1];
inline void init() {
memset(dp, 0x3f, sizeof dp);
sz = last = 0; ++sz;
len[0] = dp[0] = 0;
link[0] = -1;
//memset(ch, 0, sizeof ch);
}
inline void insert(int c) {
int cur = sz++, p;
len[cur] = len[last] + 1;
for(p = last; ~p && !ch[p][c]; p = link[p]) ch[p][c] = cur;
if(p == -1) link[cur] = 0;
else {
int q = ch[p][c];
if(len[p] + 1 == len[q]) link[cur] = q;
else {
int clone = sz++;
len[clone] = len[p] + 1;
link[clone] = link[q];
memcpy(ch[clone], ch[q], sizeof ch[q]);
for(; ~p && ch[p][c] == q; p = link[p]) ch[p][c] = clone;
link[cur] = link[q] = clone;
}
}
last = cur;
}
inline void solve() {
init();
for(int i = 1; B[i]; ++i) insert(B[i]-'a');
int ans = MAXN-1;
for(int i = 1, c; A[i]; ++i) {
c = A[i]-'a';
for(int j = 0; j < sz; ++j) {
if(ch[j][c]) dp[ch[j][c]] = min(dp[ch[j][c]], dp[j] + 1);
else ans = min(ans, dp[j] + 1);
}
}
printf("%d
", (A[ans] && B[ans]) ? ans : -1);
}
}
namespace task4 {
int nxt[MAXN][C], pos[C], dp[MAXN];
inline void solve() {
int len = strlen(B+1);
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for(int i = len; ~i; --i) { //要循环到0
for(int c = 0; c < 26; ++c)
nxt[i][c] = pos[c];
if(i) pos[B[i]-'a'] = i;
}
int ans = MAXN-1;
for(int i = 1, c; A[i]; ++i) {
c = A[i]-'a';
for(int j = len; ~j; --j) //要循环到0
if(nxt[j][c]) dp[nxt[j][c]] = min(dp[nxt[j][c]], dp[j] + 1);
else ans = min(ans, dp[j] + 1);
}
printf("%d
", (A[ans] && B[ans]) ? ans : -1);
}
}
int main() {
scanf("%s%s", A+1, B+1);
task1::solve();
task2::solve();
task3::solve();
task4::solve();
}