「CF427D」 Match & Catch - 字符串Dp

题目链接传送门

Description

给你两个字符串S1， S2， 求S1和S2的只出现过一次的最短公共子串

Solution

字符串Dp 设

TeX parse error: Undefined control sequence \[

表示在S1中最短的以i结尾的只出现过一次的子串长度

TeX parse error: Undefined control sequence \[

同理，设

TeX parse error: Undefined control sequence \[

表示S1中以i结尾，S2中以j结尾的最长公共子串的长度，然后转移还是比较好理解的，具体见代码

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 5000 + 10;

int N, M;
char A[Maxn], B[Maxn];
int sa[Maxn], sb[Maxn], Dp[Maxn][Maxn];

inline void DP (char a[], char b[], int n, int m)
{
    memset(Dp, 0, sizeof Dp);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i] == b[j])
                Dp[i][j] = max(Dp[i][j], Dp[i - 1][j - 1] + 1);
}

int main()
{
#ifdef hk_cnyali
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
#endif
    scanf("%s%s", A + 1, B + 1);
    N = strlen(A + 1);
    M = strlen(B + 1);
    DP(A, A, N, N);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if (i != j)
                sa[i] = max(sa[i], Dp[i][j] + 1);

    DP(B, B, M, M);
    for (int i = 1; i <= M; ++i)
        for (int j = 1; j <= M; ++j)
            if (i != j)
                sb[i] = max(sb[i], Dp[i][j] + 1);

    DP(A, B, N, M);
    int Ans = -1;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
        {
            //cout<<Dp[i][j]<<" "<<sa[i]<<" "<<sb[i]<<endl;
            if (Dp[i][j] >= sa[i] && Dp[i][j] >= sb[j])
            {
                if (Ans < 0 || Ans > max(sa[i], sb[j]))
                    Ans = max(sa[i], sb[j]);
            }
        }
    cout<<Ans<<endl;
    return 0;
}