字符串：KMP

题目：28. 实现 strStr()

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

输入: haystack = "hello", needle = "ll"
输出: 2

输入: haystack = "aaaaa", needle = "bba"
输出: -1

思路

BF算法（Brute Force）

将模式串和主串进行比较，一致时则继续比较下一字符，直到比较完整个模式串。不一致时将主串后移一位，模式串则从首位开始对比。

BM算法(Boyer-Moore)

利用 BF 算法，遇到不匹配字符时，每次右移一位模式串，再重新从头进行匹配，但第一次进行字符串匹配时，abcde 都匹配成功，到 x 时失败，又因为模式串每位都不相同，思考不需要再每次右移一位，而是直接跳过这些步骤。
坏字符规则

BM 算法是从后往前进行比较，发现比较的第一个字符就不匹配，将主串这个字符称之为坏字符，而模式串右移到坏字符的后面一位。

代码

class Solution {
    public int strStr(String haystack, String needle) {
        //i代表主串指针，j模式串
        int i,j;
        //主串长度和模式串长度
        int halen = haystack.length();
        int nelen = needle.length();
        //循环条件，这里只有 i 增长
        for (i = 0 , j = 0; i < halen && j < nelen; ++i) {
            //相同时，则移动 j 指针
            if (haystack.charAt(i) == needle.charAt(j)) {
                ++j;
            } else {
                //不匹配时，将 j 重新指向模式串的头部，将 i 指向本次匹配的开始位置
                i -= j;
                j = 0;
            }
        }
        //查询成功时返回索引，查询失败时返回 -1；
        int renum = j == nelen ? i - nelen : -1;
        return renum;
    }
}

字符串：KMP

原文：https://www.cnblogs.com/luedong/p/14614337.html