一个比较有意思的DP类字符串问题。涉及到子序列问题，故为了弥补漏洞，写这个题。

题目描述

        Nore0061 is a weird Nore. Just like all Nores, Nore0061 is a string lover. Nore0061’s given name is string A and the family name is string B. One day Nore King sends Nore0061 a strange alphanumeric string S, and ask Nore0061 to find the shortest substring S’ of S such that S’ can partition into three nonintersecting subsequences {A’, B’, C’} so that A’ = A and B = B’.

输入输出格式

输入格式

        The first line contains one single alphanumeric string A(1 ≤ |A| ≤ 100). The second line contains one single alphanumeric string B(1 ≤ |B| ≤ 100). The third line contains one single alphanumeric string S(1 ≤ |S| ≤ 3000).

输出格式

        One single integer denoting the length of such shortest substring. If no such substring, just print -1 instead.

输入输出样例

Sample input

Tw
yj0mJXRiq
NuRj4mRKyTcwFKj0KmCJAFpXRiHGNq

Sample output

22

题解

        考虑动态规划。规定$dp[x][y][z]$表示：若串A前x位，串B前y位是串S前z位的两个不相交子序列，则为首位匹配的最大位置，否则为0。这样可以比较容易地推出dp数组。时间复杂度$O(l_1l_2l_3)$，$l_1、l_2、l_3$是三个串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;
char a[102], b[102], str[3005];
int dp[102][102][3005];
int l1, l2, len;

inline void getDP(int l = 1, int r = len) {
    dp[1][0][l] = str[l] == a[1], dp[0][1][l] = str[l] == b[1];
    for (int i = l + 1; i <= r; i++) {
        for (int j = 0; j <= l1; j++) {
            for (int z = 0; z <= l2; z++) {
                if (j) {
                    if (str[i] == a[j])dp[j][z][i] = max(dp[j][z][i - 1], j == 1 && z == 0 ? i : dp[j - 1][z][i - 1]);
                    else dp[j][z][i] = dp[j][z][i - 1];
                }
                if (z) {
                    int x = dp[j][z][i];
                    if (str[i] == b[z])dp[j][z][i] = max(dp[j][z][i - 1], j == 0 && z == 1 ? i : dp[j][z - 1][i - 1]);
                    else dp[j][z][i] = dp[j][z][i - 1];
                    dp[j][z][i] = max(dp[j][z][i], x);
                }
            }
        }
    }
}

int main() {
    cin >> (a + 1) >> (b + 1) >> (str + 1);
    l1 = strlen(a + 1), l2 = strlen(b + 1), len = strlen(str + 1);
    getDP();
    int ans = 30000;
    for (int i = 1; i <= len; i++)
        if (dp[l1][l2][i])ans = min(ans, i - dp[l1][l2][i] + 1);
    cout << (ans == 30000 ? -1 : ans);
    return 0;
}