最长公共子串

废话

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

题目

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

题目大意是这样子的:

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

具体的输入输出如下:

输入

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

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

输出

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

思路

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

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

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

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

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

所以,该过程的状态转移方程为:

image-20211123202741048

代码

 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]那里,导致一直查不出来具体是哪里错了,总感觉自己没错,但是结果不正确。当然,上面的题解也未必正确,毕竟也没有验证过!

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

好吧,那就到此为止吧!

0%