字符串搜索算法小结（转）

因为在网上搜寻hash算法的知识，无意中又找到一些字符串搜索算法。 由于之前已经学习过一些搜索算法，觉得应该可以归为一类。因此就写一篇文章来记录下学习的过程。

问题：

在一长字符串中找出其是否包含某子字符串。

首先当然还是简单算法，通过遍历来检索所有的可能：

public static int naiveSearch(String content, String sub) {
    for(int i = 0; i < (content.length() - sub.length() + 1); i++) {
        boolean found = true;
        for(int j = 0 ; j < sub.length(); j++) {
            if(content.charAt(i + j) != sub.charAt(j)) {
                found = false;
                break;
            }
        }

        if(found) return i;
    }

    return -1;
}

时间复杂度为 Θ((n-m+1) m)

Rabin–Karp，即hash检索法：

public static int rabinKarp(String content, String sub) {
    long hcontent = rshash(content.substring(0, sub.length()));
    long hsub = rshash(sub);

    for(int i = 0; i < (content.length() - sub.length()); i++) {
        //hcontent = rshash(content.substring(i, sub.length() + i));

        if(hsub == hcontent) {
            if(sub.equals(content.substring(i, i + sub.length()))) {
                return i;
            }
        }

        hcontent = newhash(content, hcontent, i + 1, sub.length());
    }

    return -1;
}

private static long rshash(String str)
{
   int a = 63689;
   long hash = 0;

   for(int i = 0; i < str.length(); i++)
   {
      hash += a * str.charAt(i);
   }
   return hash;
}

private static long newhash(String str, long previous, int i, int length)
{
   int a = 63689;

   long minHash = str.charAt(i - 1) * a;

   long plusHash = str.charAt(i + length - 1) * a;

   return (previous - minHash + plusHash);
}

这个算法的核心思想是，通过hash值，我们可以一次匹配一整条字串，速度上要快很多。
关键： 选择这样一种hash算法，使得从前一个hash值到后一个hash值仅需要常量的步骤。

我这里实现的hash算法可以做到这点，但是有效性并不高，应该还有其他的hash算法可以更好了减少冲突的发生。

KMP算法
KMP算法说简单也不简单，说复杂也不复杂。只要你理解了它的核心思想，代码量其实非常少。可是想要解释它的思想，却也不是一件容易的事情。

考虑再三，还是觉得自己无法胜任这个解释工作，于是找了一篇自己认为解释KMP算法比较透彻的文章，翻译出来，看看大家有没有更哈的建议。

KMP algorithm
http://en./wiki/Knuth-Morris-Pratt_algorithm

实例
为了解释该算法的细节，我们首先利用一个实例来把算法的步骤过一遍。在这个过程中的任意时间点，该算法的状态都由两个变量来决定， m和i。 m代表在S中，某个对于W（pattern）匹配的起始位置。 i代表在W中的当前正在进行匹配工作的位置。我们来描述一下当算法开始时的状态：
             1         2 
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

我们首先从0位开始匹配W和S中平行的字符串，如果匹配，则前进到下一位。然而当我们到第四步的时候，我们发现S[3]是空格而W[3]=‘D’，出现了第一个不匹配。在传统的模式匹配算法中，接下来我们应该从S[1]的位置重新开始匹配。然而，如果我们仔细观察，在S的0到3位中（也就是我们刚刚进行过匹配成功的位），除了0位，其它都没有‘A‘出现过。而假设某字符串中有和W匹配的子串，那么这个子串必须是以’A‘开头的。因此，我们可以确定，S的0到3位中，都不可能存在这样的子串，于是我们决定从S的4位中重新找起。也就是说，m=4， i=0.

             1         2 
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456


此时，我们获得了一个几乎匹配的“ABCDAB”，然后在W[6](S[10])这个位置上，我们又出现了一个不匹配。于是，我们应该继续扩大m的值去寻找下一个可能的匹配。那么m的下一个值应该设置为多少呢？

整个算法的核心就在于此，我们可以从不匹配的位置开始，即m=10，然后这并不是一个正确的选择，我们发先在S的4到10位中，第8位也是‘A’。因此，如果我们从第十位开始继续找起的话，有可能就错过了某个匹配。

S中第八位的‘A’和第九位的‘B’，分别跟W的第0第1位相匹配。KMP算法对此的处理是，新的m=8（即首位匹配的值），新的i=2（因为前两位根据统计，已经是匹配好的了）。然后我们从S的m+i开始匹配W的i位。

             1         2 
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

跟第一步类似，我们在i=2就出错了，下一步我们应该跳转到哪里呢？当然是m=11，i=0：

             1         2 
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

此时，我们又在m=17的位置上出错了，根据第二步的解释，我们这次跳到m=15而i=2：

             1         2 
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

找到该模式，算法结束，返回m的值15.

部分匹配表
如果我们刚才的分析那样，整个匹配算法的核心就在于，当某次匹配过程出现不匹配的值时，如何寻找下一个做匹配的位置(这里的位置包括两个概念，即起始位置和我们应该从哪个值开始做匹配)。这样的值当然是越大越好，因为选择的下一个匹配位置越大，我们跳过的值就越多，整个算法就越快。

如果单看我们之前的分析，好像这个确定下一个匹配位置的工作关系到S和W两张表。其实不是这样的，我们只需要对W进行一个预处理，就可以做到这点。

还是来看，当W是“ABCDABD”这样一个字串时。我们会发现除了起始位置是‘A’以外，4位的值也是‘A’，那么如果我们在某次匹配时，匹配到了W的第4位，那么下一次做匹配查找时，就应当从W第4位对应的那个字符开始：
m     123456
S ... ABCDAX...
W     ABCDABD
i     0123456
因为我们已经知道S[5]和W[4]是匹配的了，那么其实就不需要再匹配一次了。因此匹配的起始位置是m=5，但是应当从i=1那里开始进行匹配。

如果是这样的一个情况呢？
m     1234567
S ... ABCDABX..
W     ABCDABD
i     0123456
同样的道理，匹配的起始位置依然是m=5，但是应当从i=2开始匹配。

下面给出求出当从任一位出现不匹配是，应该从哪里开始从新匹配的算法：

private static void next(char[] input, int[] table) {
    int pos = 2;
    int cnd = 0;

    table[0] = -1;
    table[1] = 0;

    while(pos < input.length) {
        if(input[pos - 1] == input[cnd]) {
            table[pos] = cnd + 1;
            pos++;
            cnd++;
        } else if(cnd > 0) {
            cnd = table[cnd];
        } else {
            table[pos] = 0;
            pos++;
        }
    }
}

既然已经得到了这样一个表，那么写出整个KMP算法也不是什么难事了：

private static void next(char[] input, int[] table) {
    int pos = 2;
    int cnd = 0;

    table[0] = -1;
    table[1] = 0;

    while(pos < input.length) {
        if(input[pos - 1] == input[cnd]) {
            table[pos] = cnd + 1;
            pos++;
            cnd++;
        } else if(cnd > 0) {
            cnd = table[cnd];
        } else {
            table[pos] = 0;
            pos++;
        }
    }
}

最后两个算法分别是BM算法和有限自动机算法。昨天我花了一天的时间研究BM算法，对算法的本质有了一定的了解，但是对于如何编码还是有点困惑。