实现算法：找出两个字符串的最大公共子串。（如：abcdefg和abdefg的最大公共子串是defg)解决思路

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;



}