最长公共子串.
两个字串的最长公共子串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==0) return 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) { *n = max; return ArgB+maxJ-max+1; } else return 0;
}void main(){ char *s1 = "abcdefg"; char *s2 = "xwwdcdedjwdng"; int n; const char *p = GetSameString(s1, s2,&n); if(p) { printf("at str2's pos %d, len %d\n", p-s2, n); } else printf("No LCS\n");}- 上一篇 从今开始,好好学习一下算法!.
- 下一篇 Fft算法.