Shell's Home

Jan 16, 2007 - 3 minute read - Comments

KMP

KMP是一个给人捧滥了的算法,其实单看同时有三个发明人这点,就知道这个算法是自古华山一条路,没别的想法的。KMP的算法每步虽然难想但是自然有道理,没有别的方法的。不像排序算法,一嘟噜的算法还没完。根据各种侧重点不同有不同的算法可用。
    KMP的比较算法核心在于不回朔。我们先看一个正常的例子。
SSSSSSSSSSSSSS
TTTTT            i=0, j=1,2,3…
  TTTTT          i=1, j=1,2,3…
    TTTTT        i=2, j=1,2,3…
    我们用T去匹配S,先对齐T和S的头部,然后对比T和S。如果T的范围内,TS内容一致,则匹配成功。不成功的话就将T向后移动一个字符。再次匹配T范围内TS的内容是否一致。ij的范围最大会在0<=i<=“j    KMP算法的核心在于,如果T范围内TS的内容不一致,那么T向后移动不是一个字符,而是多个。而当前比较位置永远不向前移动。如果您写出来的算法当前比较位置向前移动了,那么肯定是写错了。
    我们假定T范围内第i个字符匹配失败(0<=i
    为什么能移动一个以上呢?Next[i]怎么确定呢?我们看一个抽象的例子:M代表匹配,N不匹配,U不知道。
MMMMMNUUUUU
TTTTTTTTTTTTTTT
  TTTTTTTTTTTTTTT
    我们可以看到,向后移动字符的时候,T自身有重合的部分。这时候有三种状况,我们先假定一种重合的状况。假定T向后移动了一些字符,P代表当前比较位置。在这个位置上TS出现了不匹配。
..MMMNUUU..
..TTTTTPTTTT..
..MMNTTTTTT..
    在这个T向后移动一些距离后,在当前比较位置前已经出现了自身和自身不匹配的状况。根据上面我们知道,当前位置以前的T和S是匹配的。那么就是说,移动了这些字符后。T当前的位置上不可能取得匹配。我们称这种情况为这个位置的自身完全不匹配。
    然后是另外一种匹配状况,符号和上面一致。
..MMMNUUU..
..TTTTTPTTTT..
..MMMNTTTT..
    这个时候,T在当前匹配位置上自身不匹配,前面位置都匹配。同理可以知道,T在滑移到这个位置后可能取得匹配。我们称这种情况为这个位置的自身部分不匹配。
    最后一种匹配情况是。
..MMMNUUU..
..TTTTTPTTTT..
..MMMMUUU..
    这个时候,T在在前面和当前位置都匹配。我们知道前面是匹配的,然而当前既然已经被证明了和S不匹配。那么滑移这些位置后,新的位置上T也不可能和S取得匹配。我们称这种情况为这个位置的自身完全匹配。
    然后我们可以回头看看比较过程了。当我们对齐TS,然后进行比较的过程中。出现了不匹配。
    注意一个问题,我们回朔是为了知道移动后的T是否仍旧匹配。所以如果我们知道T匹配不匹配,就不用回朔。
    这个时候我们不移动一次T,然后回朔。而是将T滑移一下,先滑移1位好了。假设出现了当前比较位置的自身完全不匹配或者自身完全匹配,那么滑动1位肯定也无法获得一个有效的匹配。那么就继续滑动,直到出现了自身部分不匹配,或者T已经完全的滑动到了当前位置的后面。这时候T的位置才是有可能获得匹配的位置,其余的位置就没必要浪费时间了。
    也就是说,滑移距离Next[i]是i这个位置上滑动距离逐渐增加的时候,首次出现自身部分不匹配情况的位置。如果这情况不出现,那么就设定为<1的值。操作上将整个T滑动到当前位置的后面,并且从下一个位置开始比较起。
    然后附上初始版的代码和比较过程。
int            *cul_next (char *lpTpl)
{
    unsigned int    i = 0, j = 0, l = 0;
    int            *next;

    l = strlen (lpTpl);
    next = new int[l];
    memset (next, 0, l * sizeof (int));

    for (i = 1; i < l; i++) {
        for (j = 0; j < l - i && lpTpl[j] == lpTpl[j + i]; j++);
        if (j < l - i && next[j + i] == 0)
            next[j + i] = i;
    }

    for (i = 0; i < l; i++)
        printf (“%dt”, next[i]);
    printf (“n”);

    return next;
}
int kmp (char *lpSrc, char *lpTpl)
{
    char           *lpSrc_now = lpSrc;
    char           *lpTpl_now = lpTpl;
    int            *next = cul_next (lpTpl);
    if (next == NULL)
        return -1;

    while (*lpSrc_now != “) {
        if (*lpSrc_now == *lpTpl_now) {
            lpSrc_now++;
            lpTpl_now++;
        } else {
            if (next[lpTpl_now - lpTpl] != 0) {
                lpTpl_now -= next[lpTpl_now - lpTpl];
            } else {
                lpSrc_now++;
                lpTpl_now = lpTpl;
            }
        }
        if (*lpTpl_now == “)
            break;
        printf (“%sn%sn”, lpSrc_now, lpTpl_now);
    }
    delete          next;
    if (*lpTpl_now != “)
        return 0;
    return lpSrc_now - lpSrc - strlen (lpTpl);
}
———————————————————————–
0       0       0       0       0       0       0       1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab< br />b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaa aaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaab
b
aaaaaaaaaaaaaab
ab
aaaaaaaaaaaaab
b
aaaaaaaaaaaaab
ab
aaaaaaaaaaaab
b
aaaaaaaaaaaab
ab
aaaaaaaaaaab
b
aaaaaaaaaaab
ab
aaaaaaaaaab
b
aaaaaaaaaab
ab
aaaaaaaaab
b
aaaaaaaaab
ab
aaaaaaaab
b
aaaaaaaab
ab
aaaaaaab
b
aaaaaaab
ab
aaaaaab
b
aaaaaab
ab
aaaaab
b
aaaaab
ab
aaaab
b
aaaab
ab
aaab
b
aaab
ab
aab
b
aab
ab
ab
b
ab
ab
b
b
46

Tags: algorithm program

查找重复文件 全局初始化

comments powered by Disqus