最长公共子串 // Longest Common Subsequence
子串有别于子序列, 子串是连续的, 而子序列可以不连续
/*----------------------------------------------------
题为求 最长对称子串， 实际可以转化成求最长公共子串
对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定"Is PAT&TAP symmetric?"，最长对称子串为"s PAT&TAP s"，于是你应该输出11。
输入格式：
输入在一行中给出长度不超过1000的非空字符串。
输出格式：
在一行中输出最长对称子串的长度。
输入样例：
Is PAT&TAP symmetric?
输出样例：
----------------------------------------------------*/
// 首先,是最长公共子串,而非子序列.
// 进而，对称子串，相当于求某个字符串和其逆序的公共子串，到此转化完毕
我们先看看：最长公共子序列:
用的是动态规划方法, 用一个表来记录中间过程
L[i, j] 表示两个字符串a, b a[0 ~ i], b[0 ~ j] 时的最长公共子序列
故而有状态转移方程：
Ｌ［ｉ， 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]
要特别小心，这里的ｉ， ｊ 是指子序列的长度， 而非你要比较的两个字符串的下标
所以比较的时候， 要特别处理好，字符串下标和这个子序列长度的对应关系
同理，对于最长公共子串
有状态转移方程:
Ｌ［ｉ, j] = ０ // 某个串的长度为０时 0 // a[i] != b[j] L[i - 1, j - 1] + 1 // a[i] == b[j]
状态方程如何来？ 我以后再补充吧．．自己思考一下大致也可以知道
下面给出这道题的解法， 下面有两种数组下标和串长度的方法！！
首先你要明白这张表： ０行０列代表串长度为０，那么必然最长公共子串长度为０
但是如果你直接 i =［ 0，lenA）， j = ［0，lenB）
比较 a[i]和b[j], 那么肯定会使得a[０］和b[0]处的错误处理，比如 a[0] == b[0]
显然暂时最长公共子串长度 = 1
而你的 Ｌ[0, 0] 却统一初始化为０了
// 第一种方法是统一的，虽然表是从 [0,n]填的，但是使得对应的数组比较也是从a[0, n-1]
// 第二种方法，是不太统一的，就是单独去处理边界．
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std; const int EDGE = ;
int x[EDGE][EDGE];
char a[EDGE];
int sa; // size of a int func(){
memset(x, , sizeof(x));
int i, j, t;
int maxLen = ;
for(i = ; i <= sa; ++i){ // 0已被初始化，从长度为１开始即可
for(j = sa - , t = ; t <= sa; --j, ++t){
if(a[i - ] == a[j])
x[i][t] = x[i - ][t - ] + ;
else x[i][t] = ; if(maxLen < x[i][t]) maxLen = x[i][t];
}
}
return maxLen;
} int main(){
// freopen("data.in", "r", stdin);
cin.getline(a, );
sa = (int)strlen(a);
cout<<func();
return ;
}
int func(){
memset(x, , sizeof(x));
int i, j, t;
int maxLen = ;
for(i = ; i < sa; ++i){
for(j = sa - , t = ; t < sa; --j, ++t){
if(a[i] == a[j]){
if(i == || t == ) x[i][t] = ;
if(i && t) x[i][t] = x[i - ][t - ] + ;
if(x[i][t] > maxLen) maxLen = x[i][t];
}
}
}
return maxLen;
}
第二种方法