最长公共子串

lyc 收录于题目

2021-11-23 2021-11-23 约 808 字预计阅读 2 分钟 - 条评论

废话

这是本人期中考试的一道题目，本人以为最后已经做出来了（~~由于学校的评测系统压力太大，到交卷也还在等待评测~~），一直想补一下这道题，但是拖到现在才想起来。

题目

现在只能记得一个大概，下面全是个人回忆：

题目大意是这样子的：

总的要求是，给出两个串，要求输出它们的最大的公共子串长度。

具体的输入输出如下：

输入

第一行输入数字k,代表要进行k次比较

第二行输入两个字符串a,b

输出

k 行，分别表示各对串的最长公共子串长度

思路

这是一个动态规划的题目，做法与 {% post_link 题目/最短编辑距离最短编辑距离 %} 那一题相似，还比那一题要简单一些，但是为什么考试时我没做出来，我也说不上来（~~不想承认自己菜的事实~~）。下面说思路：

最大公共子串长度，给出两个串，当时我自然而然就想到了和最短编辑距离那一题相似。

用dp[i][j]表示a的前i个字串和b的前j个字串的公共子串长度。

我们假设a的前i-1个字符和b的前j-1个字符已经比较好了，现在来决策i和j：

如果当前a[i]==b[j],那么公共子串长度=dp[i-1][j-1]+1
如果不等，那么dp[i][j]=0，为什么？因为是公共子串，你到这里不等了，自然也就不能用前面的数据了，这能从头算起了。

所以，该过程的状态转移方程为：

代码

 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


/* 最长公共子串 */
#include <string.h>

#include <iostream>
using namespace std;

const int N = 1e3;
int dp[N][N],k;
char a[N], b[N];
int main() {
    cin >> k;
    while(k>0){
    scanf("%s %s", a, b);
    int n = strlen(a), m = strlen(b);
    int ans=0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] != b[j-1])               //注意此处，字符串是从0开始的，所以要-1
                dp[i][j] = 0;
            else {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            ans=max(ans,dp[i][j]);
        }
    }
    cout << ans << endl;
    k--;
    }
    return 0;
}

总结

现在回想起来感觉自己错的地方可能是错在那个a[i-1]!=b[j-1]那里，导致一直查不出来具体是哪里错了，总感觉自己没错，但是结果不正确。当然，上面的题解也未必正确，毕竟也没有验证过！

所以，写代码的时候一定要注意这种数组边界的地方，一不小心就会吃大亏。

好吧，那就到此为止吧！