首页 > 代码库 > 求最长公共子串 Longest Common Subsequence
求最长公共子串 Longest Common Subsequence
最长公共子串 // Longest Common Subsequence
子串有别于子序列, 子串是连续的, 而子序列可以不连续
/*----------------------------------------------------
对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定"Is PAT&TAP symmetric?",最长对称子串为"s PAT&TAP s",于是你应该输出11。
输入格式:
输入在一行中给出长度不超过1000的非空字符串。
输出格式:
在一行中输出最长对称子串的长度。
输入样例:
Is PAT&TAP symmetric?
输出样例:
11
----------------------------------------------------*/
// 首先,是最长公共子串,而非子序列.
// 其次,注意函数以下标为操作 故而为 [0, n - 1] 初始化记录数组要小心!,理应 -1行列全是0
// 若无法完成上面的条件,则必须自己完成 0行列的赋值而脱离统一化
// 若仍要统一,注意下标的处理!!!
// 这道题的解法我是就直接当作求: a和a的逆序的 最长公共子串的长度
对于最长公共子序列:
用的是动态规划方法, 用一个表来记录中间过程
L[i, j] 表示两个字符串a, b a[0 ~ i], b[0 ~ j] 时的最长公共子序列
故而有状态转移方程:
L[i, j] =
0 // i == 0 || j == 0
L[i - 1, j - 1] + 1 // a[i] == b[j]
max{L[i, j - 1], L[i - 1, j]} // a[i] != b[j]
要特别小心,这里的i, j 是指子序列的长度, 而非你要比较的两个字符串的下标
所以比较的时候, 要特别处理好,字符串下标和这个子序列长度的对应关系
同理,对于最长公共子串
有状态转移方程:
L[i, j] =
0 // a[i] != b[j]
L[i - 1, j - 1] + 1 // a[i] != b[j]
状态方程如何来? 我以后再补充吧..自己思考一下大致也可以知道
下面给出这道题的解法, 下面的注释和真正的内容,是两种处理 数组下标和串长度的方法!!
首先你要明白这张表: 0行0列代表串长度为0,那么必然最长公共子串长度为0
但是如果你直接 i = 0 -> lenA, j = 0 -> lenB
比较 a[i]和b[j], 那么肯定会使得a[0]和b[0]处的错误处理,比如 a[0] == b[0]
显然暂时最长公共子串长度 = 1
而你的 L[0, 0] 却统一初始化为0了
// 第一种方法,是不太统一的,就是单独去处理边界.
// 没注释的第二种方法是统一的,虽然表是从 [0,n]填的,但是使得
// 对应的数组比较也是从a[0, n-1]的
/*
int func1(){
memset(x, 0, sizeof(x));
int i, j, t;
int maxLen = 0;
for(i = 0; i < sa; ++i){
for(j = sa - 1, t = 0; t < sa; --j, ++t){
if(a[i] == a[j]){
if(i == 0 || t == 0) x[i][t] = 1;
if(i && t) x[i][t] = x[i - 1][t - 1] + 1;
if(x[i][t] > maxLen) maxLen = x[i][t];
}
}
}
return maxLen;
}
*/
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int EDGE = 1500;
int x[EDGE][EDGE];
char a[EDGE]; // size of a
int sa;
int func1(){
memset(x, 0, sizeof(x));
int i, j, t;
int maxLen = 0;
for(i = 1; i <= sa; ++i){
for(j = sa - 1, t = 1; t <= sa; --j, ++t){
if(a[i - 1] == a[j]){
x[i][t] = x[i - 1][t - 1] + 1;
}else{
x[i][t] = 0;
}
if(maxLen < x[i][t]) maxLen = x[i][t];
}
}
return maxLen;
}
int main(){
freopen("data.in", "r", stdin);
cin.getline(a, 1450);
sa = (int)strlen(a);
cout<<func1();
return 0;
}
求最长公共子串 Longest Common Subsequence