最长公共子串.

两个字串的最长公共子串LCS(longest common substring)算法

参考 http://www.5do8.com/blog/doc/569/index.aspx

多个字符串的LCS算法 参考 http://imlazy.ycool.com/post.1861423.html 此文给出的程序似乎有问题

两个的LCS程序

 

#include <stdio.h>
#include 
<string.h>


// return the start position in argB
// n : the length of the LCS
const char* GetSameString (char const* ArgA,char const*  ArgB, int *n ){
     
int n1=strlen(ArgA);
     
int n2=strlen(ArgB);
     
if(n1==0 || n2==0return 0;
     
     
int* CompareArr=new int[n2];
     
int max=0,maxJ=0
     
for(int iloop=0;iloop<n1;iloop++)//注意先i,再j的顺序
     {
          
for(int jloop=n2-1;jloop>=0;jloop--)//注意从大到小顺序,这是为了在DP时,新老CompareArr不会互相影响
          {
            
//这个等式很炫, 用了DP思想, 如果当前字串1的i和字串2的j相等,i或者j为0,则为1,否则为
               CompareArr[jloop]=(ArgB[jloop]==ArgA[iloop])?( (iloop==0||jloop==0)?1:CompareArr[jloop-1]+1):0;
               
if(CompareArr[jloop]>=max)
               
{
                    max
=CompareArr[jloop];
                    maxJ
=jloop;
               }

          }

     }

     
if(max>0)
     
{
        
*= max;
        
return ArgB+maxJ-max+1;
     }

     
else 
        
return 0;
}


void main()
{
    
char *s1 = "abcdefg";
    
char *s2 = "xwwdcdedjwdng";
    
    
int n;
    
const char *= GetSameString(s1, s2,&n);
    
    
if(p)
    
{
        printf(
"at str2's pos %d, len %d\n", p-s2, n);
    }

    
else
        printf(
"No LCS\n");
}

Powered by Jekyll and Theme by solid

本站总访问量