实现算法：找出两个字符串的最大公共子串。（如：abcdefg和abdefg的最大公共子串是defg)
实现算法：找出两个字符串的最大公共子串。（如：abcdefg和abdefg的最大公共子串是defg)
[解决办法]
这样的问题就……
不懂的先google it 吧！
穷举法、矩阵法之类的一大堆~~
[解决办法]
1.以两个字符串c1c2为行列构成矩阵a，相同a[i][j]为1...最大就是斜方向连续1最多的
2.两个字符串c1c2，从大到小在a1中取子串，和c2匹配
[解决办法]
int KMPIndex(strtype s,strtype t){ int i,j,v; i = 0; j = 0; while (i<s.length&&j<t.length) { if (j==-1||s.str[i]==t.str[j]) { i++; j++ } else j=next[j]; } if(j>=t.length) v=i-t.length; else v = -1; return(v);}
[解决办法]
DP(动态规划)解:
时间空间复杂度分析
如果用n,m表示两个字符串的长度的话，那么算法的
时间复杂度为O(n*m),空间复杂度也为O(n*m)
附：完整的源程序g++编译通过
#include <stdio.h>
#include <string.h>
void print_table(char *str1,char *str2,int **pf)
{
int i,j,row,col;
row = strlen(str1);
col = strlen(str2);
printf("\t\t");
for (i=0; i<col; i++)
printf("%c\t",str2[i]);
for (i=0; i<=row; i++)
{
for (j=0; j<=col; j++)
{
if (j == 0)
{
printf("\n");
if (i)
printf("%c\t",str1[i-1]);
else
printf("\t");
}
printf("%d\t",pf[i][j]);
}
}
}
int commstr(char *str1, char *str2)
/* 返回str1,str2的最长公共之串长度*/
{
int len1=strlen(str1),len2=strlen(str2),row,col,max=0;
int **pf = new int*[len1+1];//动态分配一个二维数组作为辅助空间
for (row=0; row<len1+1; row++)
pf[row] = new int[len2+1];
//数组赋初值
for (row=0; row<len1+1; row++)
pf[row][0] = 0;
for (col=0; col<len2+1; col++)
pf[0][col] = 0;
for (row=1; row<=len1; row++)
for (col=1;col<=len2; col++)
{
if (str1[row-1] == str2[col-1])
{
pf[row][col] = pf[row-1][col-1] + 1;
max = pf[row][col] > max ? pf[row][col] : max;
}
else
pf[row][col] = 0;
}
print_table(str1,str2,pf);
//空间回收
for (row=0; row<len1+1; row++)
delete[] pf[row];
delete[] pf;
return max;
}
int main(int argc,char **argv)
{
if (argc >= 3)
{
printf("String:\n\t1. %s\n\t2. %s\n",argv[1],argv[2]);
printf("\nmax substr length:%d\n",commstr(argv[1],argv[2]));
}
return 0;
}