如何实现两个串的最大匹配，（已给出算法）

Question

请教谁能用ＶＣ来实现以下的算法？http://www.welnature.com/strcmp.htm字符串的模式匹配主要用于文本处理，例如文本编辑。文本数据的存储（文本压缩）和数据检索系统。所谓字符串的模式匹配[2]，就是给定两个字符串S和T，长度分别为m和n，找出T中出现的一个或多个或所有的S，在这方面已经取得了不少进展[3][4][5][6][7][8][9][10][11]。本文从文本处理的另一个角度出发，找出两个串的最大匹配，比较其相似程度[1]。它主要应用于文本比较，特别是在计算机辅助教学中。显然前者要找S的完全匹配，而后者并无此要求。例如，若S=ABCD，T=EFABCDX，那么模式匹配的结果就是找出了T中的一个ABCD，而我们算法的结果就是S能与T的ABCD完全匹配，但是T中还有3个字符是比S多出来的，也就是说在S中有100%的字符与T中的匹配，而在T中有57%的字符与S中的匹配。若S= ABCDFE，T=AFXBECDY。则在模式匹配中S与T无匹配项，但在我们的算法中就能发现T中存在A，B，C，D，但D后不存在E，F。而且S中也存在A，B，C，D，且具有顺序性。这样就能公正地评价S，T的区别。得知其相似程度。
http://www.welnature.com/strcmp.htm

Answer 1

用BMP算法 比较好的
这个一般酸法书上有的,自己找找看.vc程序吗,可以在www.codeproject.com 上找

Answer 2

你说这个算法有一定的智能性，不过如果真的用算法实现起来要相当的复杂。象你举的那个例子，若S= ABCDFE，T=AFXBECDY 你说它们都有 ABCD且都有相同的顺序，但它的半径要有一个长度范围，如T=Axxx(5个)yy(10个)BCD 当然里面的其它字符的个数还可以更多，如果相隔太远了就不具有意义了。还有如果T比较长的情况下，中间还会夹杂些其它相似的部分，那样的话，你是不是要用全排列把各种可能的情况都考虑到，那样的话，如果字串很长的话，那么其计算量将会是相当大的。

Answer 3

#include <string.h>
#include<iostream.h>
void str_cmp(char* st1,char* st2,char* str);void main(void)
 {
         char* st1="aasffghaahddh";
         char* st2="acdfffhd";
char* sta=new char[strlen(st1)+1];
         char* stb=new char[strlen(st2)+1];
         str_cmp(st1,st2,sta);
         str_cmp(st1,st2,stb);
cout<<sta<<endl;
         cout<<stb<<endl;
delete sta;
         delete stb;
}
void str_cmp(char* st1,char* st2,char* str)
{
int n=-1;
while(st1[0]!='\0')
{
int j=0;
while(st2[j]!='\0')
{
if(st2[j]==st1[0]) 
{
n++;
str[n]=st1[0];
st2+=j+1;
break;
}
j++;
}
st1++;
}
str[n+1]='\0';
}

Answer 4

本人回头看了http://www.welnature.com/strcmp.htm，不过是把问题复杂化了，上面的程序可以说明一切，按字典序匹配就是自然的最大匹配。

Answer 5

将上面的用法换一下
void main(void)
{
char* st1="aasffghacahddh";
char* st2="acdfffhd";
char* sta=new char[strlen(st1)+1];
char* stb=new char[strlen(st2)+1];
str_cmp(st1,st2,sta);
str_cmp(st2,st1,stb);// 原先的在这里不妥。
cout<<sta<<endl;
cout<<stb<<endl;
delete[] sta;
         delete[] stb;
}

Answer 6

如果是这两个字串,S=ABCDEFGHI,T=ABCDFGEHI,
会是怎样的结果呢?

Answer 7

AECDEF
AFBCDE
sta(AE)
stb(AF)