精华区文章阅读

发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标  题: [合集]求两个串的匹配子串有什么比较好的算法？
发信站: 哈工大紫丁香 (2001年08月27日07:10:42 星期一), 站内信件

────────────────────────────────────────
xingchen (好像一条狗)                于 2001年08月20日08:58:34 星期一说道:

要求能将源串中的能匹配的子串的长度都标记出来。
eg: 源串：b d a b c b a b b c 模式串：a b c
结果因为：1 0 3 2 1 1 2 1 2 1
多谢。

────────────────────────────────────────
ssos (存在与虚无·戒酒戒网)          于 2001年08月20日09:01:44 星期一说道:

KMP算法

────────────────────────────────────────
xingchen (好像一条狗)                于 2001年08月20日09:09:06 星期一说道:

我记得KMP算法只能从模式串的头部进行比较。这样的话我的例子的
结果只能是：b d a b c b a b b c
            0 0 3 2 1 0 2 1 0 0
   或者是   0 0 1 2 3 0 1 2 0 0

────────────────────────────────────────
ssos (存在与虚无·戒酒戒网)          于 2001年08月20日09:23:14 星期一说道:

我知道你的意思了,这样的要求现成的算法我不知道
好像是可以模仿把比较串和模式串都倒过来,按照类似KMP算法进行匹配

────────────────────────────────────────
xingchen (好像一条狗)                于 2001年08月20日09:48:08 星期一说道:

多谢ssos。
不过倒过来也不行，因为倒过来又要要求从最后一个字符开始匹配。
我现在唯一的思路是将模式串循环移位，依次利用KMP算法进行匹配。
这样得到的算法的复杂度是O((n+m)*m)。有没有什么更好的算法了？
似乎应该可以利用上次KMP的匹配结果来对本次的匹配进行优化。

────────────────────────────────────────
xingchen (好像一条狗)                于 2001年08月20日09:56:04 星期一说道:

算了吧，其实这个复杂度也可以接受了。再次谢谢ssos.

────────────────────────────────────────
sino (茶水先生)                      于 2001年08月20日11:46:30 星期一说道:

匹配问题的复杂度没有什么突破，不过构造自动机的方法应该是效率最高的了。
问题的规模是多少？

────────────────────────────────────────
yangzhongwei (//smile to all)        于 2001年08月20日13:16:24 星期一说道:

这个问题使用perl语言强大的模式匹配能力，可以很容易求出。
下面的这个程序是我用perl写的，已经调试通过了，供参考。
(注：如要计算其他的题，只需将源串赋值给$d_string,模式串
赋值给$s_string即可）
$d_string="bdabcbabbc";
$s_string="abc";
print ($d_string);
print ("\n");
for ($count=0;$count<length($d_string);$count++)
    {
        $tmp=substr($d_string,$count);
        for ($count2=length($s_string);$count2>=0;$count2=$count2-1)
        {
            $tmp2=substr($tmp,0,length($s_string)-$count2+1);
            if ($s_string!~/$tmp2/)
                {
                print (length($s_string)-$count2);
                goto ee;
                }
        }
        print (length($tmp2));
        ee:
    }
运行结果：
bdabcbabbc
1032112121

────────────────────────────────────────
deem (摩亚迪·沙丘男爵)              于 2001年08月20日20:43:21 星期一说道:

我想大家讨论这一题的意义不在于能不能求出吧！
而是是想找出一种优化算法来求解，不知道我说的
对不对！

────────────────────────────────────────
lizhenguo (夸父·追日)               于 2001年08月20日21:39:21 星期一说道:

为什么是这个结果呢？

────────────────────────────────────────
sino (茶水先生)                      于 2001年08月21日12:15:21 星期二说道:

是的，重点在于思路方法

────────────────────────────────────────
Lerry (Lerry)                        于 2001年08月21日13:23:52 星期二说道:

这个复杂度为O(M*N)
#include "stdio.h"
#include "string.h"
main(void)
{
    int i,j,pp,m,n;
    char* test="bdabcbabbc";
    char* dest="abc";
    m=strlen(test);
    n=strlen(dest);
    char* org =new char[m+n];
    int * flag=new int [m+n];
    strcpy(org,dest);
    strcpy(org+n,test);
    for(i=0;i<m+n;flag[i++]=0);
    for(i=1;pp=0,i<=m;i++)
        for(j=n-1;j>=0;j--)
            if(dest[j]==org[i+j])
                flag[i+j]+=++pp;
    for(i=n;i<m+n;i++)
        printf("%d",flag[i]);
    printf("\n");
    return 0;
}

────────────────────────────────────────

Algorithm 版 (精华区)