E3 最长公共子串 • EH's Blog

题目情境#

题目描述

给出一个长度为 $n(n\le 5000)$ 的字符串序列。请输出这个序列的最长公共子串及其长度。

输入格式

输入两个字符串（代码里忽略了这个）。

输出格式

输出一个整数表示最长公共子串的长度，

算法解析：#

最长公共子串： $f[i][j]$ 表示以 $a[i]$ 、 $b[j]$ 结尾的最长公共子串长度。若 $a[i]==b[j]$ ， $f[i][j]=f[i-1][j-1]+1$ ；否则 $f[i][j]=0$ （子串要求连续，一旦不等就断开）。答案取所有 $f[i][j]$ 的最大值。复杂度 $O(n^2)$ 。

Python代码实现#

a = "BCCABCCB"
b = "AACCAB"
m = len(a)
n = len(b)
f = [[0] * (n + 1) for _ in range(m + 1)]
ans = 0
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if a[i - 1] == b[j - 1]:
            f[i][j] = f[i - 1][j - 1] + 1
        else:
            f[i][j] = 0
        ans = max(ans, f[i][j])
print(ans)

python

C++代码实现#

#include<iostream>
#include<cstring>
using namespace std;

char a[200]="BCCABCCB";
char b[200]="AACCAB";
int f[201][201];

int main(){
  int ans=0;
  for(int i=1; i<=strlen(a); i++){
    for(int j=1; j<=strlen(b); j++){
      if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;
      else f[i][j]=0;
      ans=max(ans,f[i][j]);
    }
  }
  printf("ans=%d\n",ans);
  return 0;
}