hanyeah

字符串匹配，就是字符串查找，查找字符串t在s中的起始位置。比如编程语言中经常用到的一个API，通常是叫indexOf。各种文本编辑器中的ctrl+f查找功能。

实际应用的时候，当然直接调用API 就可以了，但是学习一下实现原理还是很有好处的。

最简单最容易想到的就是双层循环，穷举式的匹配了。（程杰的大话数据结构中称作：朴素的模式匹配算法）

/**
 * 朴素的模式匹配算法。
 */
function nomalIndexOf(s, t) {
    var i = 0;
    var j = 0;
    var len1 = s.length;
    var len2 = t.length;
    while (i < len1 && j < len2) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= len2) {
        return i - len2;
    } else {
        return - 1;
    }
}

这个比较简单，写法也多种多样，不用看任何文章都可以自己手写出来。就不赘述了。

然而，人们研究算法并不局限于实现功能，还要考虑效率问题。好多大牛研究出了好多高效率的算法，很神奇。

KMP算法就是其中比较出名的一个。

关于原理的介绍，这篇写的不错：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

如果能看得懂英文，去看作者的原始论文就更好了。

这篇文章对于算法的原理已经讲解的很详细了，KMP算法的难点在于next数组的创建，文中没有具体实现。可以单独搜索，学习，实践。

下面是我的实现，仅供参考，还是要自己理解了写一遍，才有效果。

function getNext(t) {
    var arr = [0];
    var i = 1;
    var j = 0;
    var len = t.length;
    while (i < len) {
        if (t[i] == t[j]) {
            arr[i] = j + 1;
            i++;
            j++;
        } else {
            arr[i] = 0;
            i++;
            j = 0;
        }
    }
    return arr;
}
function kmpIndexOf(s, t) {
    var len1 = s.length;
    var len2 = t.length;
    var i = 0;
    var j = 0;
    var k = 0;
    var next = getNext(t);
    //console.log(next);
    while (i < len1 && j < len2) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            if (j == 0) {
                i++;
            } else {
                i = i - next[j]; //i=(i-j)+(j-next[j]);
            }
            j = 0;
        }
    }
    if (j >= len2) {
        return i - len2;
    }
    return - 1;
}