子字符串的定義和子串的定義類似，但要求是連續分布在其他字符串中。比如輸入兩個字符串BDCABA和ABCBDAB的最長公共字符串有BD和AB，它們的長度都是2。
最長公共子字符串共有兩種解決方法，下面具體說說我的思路
方法一：
Longest Common Substring和Longest Common Subsequence是有區別的
X = <a, b, c, f, b, c>
Y = <a, b, f, c, a, b>
X和Y的Longest Common Sequence為<a, b, c, b>，長度為4
X和Y的Longest Common Substring為 <a, b>長度為2
其實Substring問題是Subsequence問題的特殊情況，也是要找兩個遞增的下標序列
<i1, i2, ...ik> 和 <j1, j2, ..., jk>使
xi1 == yj1
xi2 == yj2
......
xik == yjk
與Subsequence問題不同的是，Substring問題不光要求下標序列是遞增的，還要求每次
遞增的增量為1， 即兩個下標序列為：
<i, i+1, i+2, ..., i+k-1> 和 <j, j+1, j+2, ..., j+k-1>
類比Subquence問題的動態規劃解法，Substring也可以用動態規劃解決，令
c[i][j]表示Xi和Yi的最大Substring的長度，比如
X = <y, e, d, f>
Y = <y, e, k, f>
c[1][1] = 1
c[2][2] = 2
c[3][3] = 0
c[4][4] = 1
動態轉移方程為：
如果xi == yj， 則 c[i][j] = c[i-1][j-1]+1
如果xi ! = yj, 那麼c[i][j] = 0
最後求Longest Common Substring的長度等於
max{ c[i][j], 1<=i<=n， 1<=j<=m}
完整的代碼如下：
代碼如下：
/**
找出兩個字符串的最長公共連續子串的長度
** author :liuzhiwei
** data:2011-08-16
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int longest_common_substring(char *str1, char *str2)
{
int i,j,k,len1,len2,max,x,y;
len1 = strlen(str1);
len2 = strlen(str2);
int **c = new int*[len1+1];
for(i = 0; i < len1+1; i++)
c[i] = new int[len2+1];
for(i = 0; i < len1+1; i++)
c[i][0]=0;//第0列都初始化為0
for(j = 0; j < len2+1; j++)
c[0][j]=0;//第0行都初始化為0
max = -1;
for(i = 1 ; i < len1+1 ; i++)
{
for(j = 1; j < len2+1; j++)
{
if(str1[i-1]==str2[j-1])//只需要跟左上方的c[i-1][j-1]比較就可以了
c[i][j]=c[i-1][j-1]+1;
else//不連續的時候還要跟左邊的c[i][j-1]、上邊的c[i-1][j]值比較，這裡不需要
c[i][j]=0;
if(c[i][j]>max)
{
max=c[i][j];
x=i;
y=j;
}
}
}
//輸出公共子串
char s[1000];
k=max;
i=x-1,j=y-1;
s[k--]='\0';
while(i>=0 && j>=0)
{
if(str1[i]==str2[j])
{
s[k--]=str1[i];
i--;
j--;
}
else //只要有一個不相等，就說明相等的公共字符斷了，不連續了
break;
}
printf("最長公共子串為：");
puts(s);
for(i = 0; i < len1+1; i++)//釋放動態申請的二維數組
delete[] c[i];
delete[] c;
return max;
}
int main(void)
{
char str1[1000],str2[1000];
printf("請輸入第一個字符串：");
gets(str1);
printf("請輸入第二個字符串：");
gets(str2);
int len = longest_common_substring(str1, str2);
printf("最長公共連續子串的長度為：%d\n",len);
system("pause");
return 0;
}
效果圖如下：
方法二：
將字符串s1和s2分別寫在兩把直尺上面(我依然用s1，s2來表示這兩把直尺)，然後將s1固定，s2的頭部和s1的尾部對齊，然後逐漸移動直尺s2，比較重疊部分的字符串中的公共子串的長度，直到直尺s2移動到s1的頭部。在這個過程中求得的最大長度就是s1、s2最大子串的長度。
下圖是求解過程的圖示（下圖有點錯誤，應該是將s2從右往左移動），藍色部分表示重疊的字符串，紅色的部分表示重疊部分相同的子串
其中s1="shaohui"，s2="ahui"，最後求得的結果為3
完整的代碼如下：
代碼如下：
/**
找出兩個字符串的最長公共連續子串的長度
** author :liuzhiwei
** data :2011-08-16
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int longest_common_substring(char *str1, char *str2)
{
int i,len1,len2,len,s1_start,s2_start,idx,curmax,max;
len1 = strlen(str1);
len2 = strlen(str2);
len = len1 + len2;
max = 0;
for(i = 0 ; i < len ; i++)
{
s1_start = s2_start = 0;
if(i < len1)
s1_start = len1 - i; //每次開始匹配的起始位置
else
s2_start = i - len1;
curmax = 0;
for(idx = 0 ; ( s1_start + idx < len1 ) && ( s2_start + idx < len2 ); idx++ )
{
if(str1[s1_start+idx]==str2[s2_start+idx])
curmax++;
else //只要有一個不相等，就說明相等的公共字符斷了，不連續了，要保存curmax與max中的最大值，並將curmax重置為0
{
max = curmax > max ? curmax : max;
curmax = 0;
}
}
max = curmax > max ? curmax : max;
}
return max;
}
int main(void)
{
char str1[1000],str2[1000];
printf("請輸入第一個字符串：");
gets(str1);
printf("請輸入第二個字符串：");
gets(str2);
int len = longest_common_substring(str1, str2);
printf("最長公共連續子串的長度為：%d\n",len);
system("pause");
return 0;
}
效果圖如下：
稍微改動一下，便可以輸出公共子串了，就是要保存一下連續公共子串最後一個字符在其中一個字符串中的下標位置：
代碼如下：
/**
找出兩個字符串的最長公共連續子串的長度
** author :liuzhiwei
** data :2011-08-16
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int longest_common_substring(char *str1, char *str2)
{
int i,k,len1,len2,len,s1_start,s2_start,idx,curmax,max;
len1 = strlen(str1);
len2 = strlen(str2);
len = len1 + len2;
max = 0;
for(i = 0 ; i < len ; i++)
{
s1_start = s2_start = 0;
if(i < len1)
s1_start = len1 - i; //每次開始匹配的起始位置
else
s2_start = i - len1;
curmax = 0;
for(idx = 0 ; ( s1_start + idx < len1 ) && ( s2_start + idx < len2 ); idx++ )
{
if(str1[s1_start+idx]==str2[s2_start+idx])
curmax++;
else //只要有一個不相等，就說明相等的公共字符斷了，不連續了，要保存curmax與max中的最大值，並將curmax重置為0
{
//max = curmax > max ? curmax : max;
if(curmax > max)
{
max = curmax;
k = s1_start+idx-1; //保存連續子串長度增加時連續子串最後一個字符在str1字符串中的下標位置，便於輸出公共連續子串
}
curmax = 0;
}
}
//max = curmax > max ? curmax : max;
if(curmax > max)
{
max = curmax;
k = s1_start+idx-1;
}
}
//輸出公共子串
char s[1000];
for(i=0;i<max;i++)
s[i]=str1[k-max+1+i]; //公共字串在str1中的下標起始位置為k-max+1，結束位置為k
s[i]='\0';
printf("最長公共子串為：");
puts(s);
return max;
}
int main(void)
{
char str1[1000],str2[1000];
printf("請輸入第一個字符串：");
gets(str1);
printf("請輸入第二個字符串：");
gets(str2);
int len = longest_common_substring(str1, str2);
printf("最長公共連續子串的長度為：%d\n",len);
system("pause");
return 0;
}
效果圖如下：
擴展：子串也可以是反串，比如HDOJ 1238
題目意思是要搜索最長的子串
給出一系列字符串,幾個子串可以是反串
rose
orchid
這裡最長的子串是 ro 跟or 長度為2。
如果窮舉搜索的話,肯定過不了。
所以可以找出所有字符串中最短的串,枚舉最短的字符串的子串
判斷是否都是別的字符串的子串，求出最大長度即可。。
代碼如下：
/**
找出兩個字符串的最長公共連續子串的長度
** author :liuzhiwei
** data :2011-08-16
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
char str[100][100];
int k;
int match(int start,int end,int n) //最短字符串中的起點下標、終點下標，字符串總數
{
int i,j,len,p,h;
for(i=0;i<n;i++)
{
if(i==k)
continue;
len=strlen(str[i]);
for(j=0;j<=len-1-end+start;j++) //str[i]字符串可以組成len-1-end+start個長度為end-start的連續子串
{
for(p=start,h=j;p<=end;p++,h++) //順序判斷子串
{
if(str[k][p]!=str[i][h]) //不等即跳出
break;
}
if(p>end) //如果全部相等，則匹配成功，終止
break;
for(p=end,h=j;p>=start;p--,h++) //逆序判斷子串
{
if(str[k][p]!=str[i][h]) //不等即跳出
break;
}
if(p<start) //如果全部相等，則匹配成功，終止
break;
}
if(j>len-1-end+start) //如果搜索完畢都沒終止,即無匹配
return 0;
}
return 1;
}
int main(void)
{
int t,i,j,n,len,minlen,flag;
scanf("%d",&t);
while(t--)
{
minlen=1000,flag=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",str[i]);
len = strlen(str[i]);
if(len<minlen)
{
minlen=len; //保存最短字符串的長度
k=i; //保存最短字符串的序號
}
}
for(i=0;i<minlen;i++) //對最短字符串的連續字串進行匹配查找
{
for(j=0;j<=i;j++)
{
if(match(j,j+minlen-1-i,n)) //子串是否匹配
{
flag=1;
break;
}
}
if(flag==1)
break;
}
printf("%d\n",minlen-i);
}
system("pause");
return 0;
}
