题解 P3082 【[USACO13MAR] Necklace G】

· · 题解

upd on 25.10.30： 修改代码中小错误，感谢 @chenzhaoxu2027指出问题

Solution

正难则反，将问题转化成留下一个长度最长的 a 的子串，使得 b 不在其中出现过。

设 f_{i,j} 表示 a 串前 i 个字符，正好匹配到 b 串第 j 个字符，最多可保留的位数。

考虑从 f_i 转移到 f_{i + 1}，转移方程为:

f_{i+1,k} = \max\{f_{i+1,k},f_{i,j} + 1\}

其中 k 表示添加了字符 a_{i + 1} 之后，正好匹配到 b 串的位置。

之后问题的难点就在于如何快速的求出每一个 f_{i,j} 对应的 k。

记 g_{i,j} 表示已经正好匹配到 b 串第 i 个字符，再添上字符 j 所匹配到的位置，也就是上文的 k。

先对 b 串跑一边 \text{KMP}，预处理出 next 数组，考虑 g 的转移。

g_{i,j} = \begin{cases} i + 1 &b_{i + 1} = j\\g_{next_i,j} & otherwise \end{cases}

综上有：

f_{i+1,g_{j,a_{i + 1}}} = \max\{f_{i+1,g_{j,a_{i + 1}}},f_{i,j} + 1\}

初值：

f_{i,j} = f_{i - 1,j}

时间复杂度 O(nm)。

code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
const int maxm = 1e3 + 5;
int n,m,f[maxn][maxm],ans,g[maxm][30],kmp[maxm];
char a[maxn],b[maxm];
void input()
{
    scanf("%s%s",a + 1,b + 1);
    n = strlen(a + 1),m = strlen(b + 1);
}
void prefix()
{
    int j = 0;
    for(int i = 2;i <= m;i++)
    {
        while(j&&b[i] != b[j + 1])
            j = kmp[j];
        kmp[i] = b[i] == b[j + 1] ? ++j : 0;
    }
    for(int i = 0;i < m;i++)
        for(int j = 1;j <= 26;j++)
            g[i][j] = (b[i + 1] == j + 'a' - 1) ? i + 1 : g[kmp[i]][j];
}
void DP()
{
    for(int i = 0;i < n;i++)
    {
        if(i)
            for(int j = 0;j <= m;j++)
                f[i][j] = max(f[i][j],f[i - 1][j]);
        for(int j = 0;j < m;j++)
                f[i + 1][g[j][a[i + 1] - 'a' + 1]] = max(f[i + 1][g[j][a[i + 1] - 'a' + 1]],f[i][j] + 1);
    }
}
void output()
{
    for(int i = 0;i < m;i++)
        ans = max(ans,f[n][i]);
    printf("%d",n - ans);
}
int main()
{
    input();
    prefix();
    DP();
    output();
    return 0 ;
}