codeforce catching cheaters超时

Question

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 5010;
const int mini = 250;
char X[maxn], Y[maxn];
int dp[mini][mini];
int main() {
    int n, m;
    while (scanf("%d%d",&n,&m)==2){
        int max_ = 0;
        memset(dp, 0, sizeof(dp));
        scanf("%s", X); scanf("%s", Y);
        for(int i=1;i<=n;++i)
            for (int j = 1; j <= m; ++j)
            {
                if (X[i - 1] == Y[j - 1])dp[i][j] = (i == 0 || j == 0) ? 1 : dp[i - 1][j - 1] + 2;
                else dp[i][j] = max(0, max(dp[i - 1][j], dp[i][j - 1]) - 1);
                max_ = max(max_, dp[i][j]);
            }
        printf("%d\n", max_);
    }
}

不太明白，是哪里出了问题，整体思路看上去没啥问题呀？

Answer 1

原因是你使用了 $O(nm)$ 的时间复杂度的算法，其中 $n$ 和 $m$ 分别为字符串 $X$ 和字符串 $Y$ 的长度。这个算法的时间复杂度可能在某些较长的测试用例下表现不佳。
如果要优化时间复杂度，可以考虑使用一些高效的字符串匹配算法，例如 KMP 算法或者 Boyer-Moore 算法，它们的时间复杂度分别为 $O(n+m)$ 和 $O(n)$，可以显著地提高代码的运行效率