LeetCode-No-28-(KMP)

实现 strStr() 函数

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

示例 1:

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

示例 2:

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

说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

显然这题主要目标是在主串中找到一个模式串，而我在数据结构课中有学到KMP算法，因此我首选题解就是实现KMP。

KMP （主要思想：不回退的主串查找位，有效利用失败信息）

暴力法存在的问题

主串abcdabcdabce，模式串abcdabce. 标志位 i，j

我们可以知道第一次匹配会在abcdabcdabce，abcdabce处失败 在暴力法中，失败后 i ++，j=0，从i=1，j=0 处再次开始一轮匹配。 即主串明明匹配到了第8位，失败后却还要回退到第二位开始新的匹配，无疑浪费了很多时间。

失败返回的有效信息

模式串在 e 处失败，可以带给我们什么有效信息：

1. 主串前面有abcdabc
2. 主串这一位不为e

利用返回的有效信息

已经已知主串有了这七个字符，按人的思维去分析的话，可以知道主串前四位abcd都没必要去做新的匹配模式串的循环了，因为一定会失败，而5 ~ 7位abc虽然是在匹配模式串的5 ~ 7位匹配出来的，但是却也可以匹配模式串的前三位。因为这些都是已知信息，所以我们可以直接当失败处abcdabcd已经匹配了模式串的abc，只需要拿d去匹配d即可。

相当于不仅没回退，还可以在当前位置上直接跳过模式串前三位进行后续匹配。

而把上面的思路写成逻辑，我们就需要分析其产生的原因条件，以及导出的结果

为什么恰巧可以跳过呢？让我们来看一下跳过时的环境条件

1. 失败前的倒数几位，刚好可以拿去匹配正数前几位，因此相当于匹配好了前几位
2. 这种在某一位失败之后能否产生跳跃的信息，只和模式串本身有关，和主串无关，因为我们是用失败的倒数几位去匹配前几位，全是模式串自己。

因此我们可以找到跳过的思路，对于匹配失败时：

1. 假如模式串在这个字符之前的倒数几位能和整数几位匹配，那就直接略过，i 不变，j 跳到整数几位的后一位接着匹配
2. 假如不能形成这种前后缀的匹配，则直接让 i ++，在下一位开始全新的匹配

i 不用回到这次匹配的开头再i++，假如回到开头再 i++ ，我们的目标是当前匹配失败了，主串字符串匹配区间右移一位是不是能匹配成功。然而这种匹配成功的条件必须是区间右移后，和移动前的重叠区域字符相同。即在重叠区域内，pat[i+1]==pat[i]。用人话翻译就是，只有str=aaaaax pat=aaaax这种前部分字符只有一个的情况才有移动区间匹配成功的可能。然而我们可以从实例中看到，这种字符串情况也包含在跳过的思路中，也恰好满足跳过的条件，甚至不用回移不用使j=0开始匹配，只需要接着从跳到的 j 处匹配就解决了这个情况。

创造跳跃数组

我们知道，KMP主要算法就是在失败时，通过跳跃到恰当的位置接着匹配。 而这个恰当的位置 k 满足：k之前的所有k位，即前缀，和失败处的倒数k位，即后缀，恰好相同，此时失败即可跳到k处。

所以我们要解决的就是，在开始查找模式串之前，先对模式串每一位 j 进行前后缀检测，存在满足的前后缀即可令 jump[j]=k 存储在该处失败可跳跃到的位置。不存在则存入 -1 作为标志即可

因为跳跃位置只与模式串本身有关，因此事先处理好一次即可对任何主串复用。

当然检测前后缀也不是一个简单的事，KMP中构造跳跃数组的过程中也是用了KMP自己.......作为学习者只能对创造者表示敬佩，这里用伪代码描述一下。

因为在0位失败肯定没法跳跃，令jump[0]=-1 
设置好跳跃定位标志 k=-1
对模式串每一位 i
    假如 i  k 位相同，或者k==-1
      即看作前后缀目前为止相同
      i, k 到下一位
      对于已经处理好前后缀之后的下一位，只需把跳跃信息给它即可
          假如下一位与跳跃位不同
              把已经处理好的k作为它的跳跃位即可，jump[i]=k
          假如下一位与跳跃位相同
              （比如在a失败，跳到的地方还是a，那就没有再比一次的必要了）
              把跳跃位的跳跃位作为它的跳跃位hhh jump[i]=jump[k]
   假如 i k 位不同 （他们的跳跃信息已经被处理好了）
      （内用KMP，即相当于后缀作为主串，前缀作为模式串，此时匹配失败了，前缀跳到跳跃位接着匹配）
      k=jump[k]
      

处理好跳跃数组（失效数组）之后，即可按数组的跳跃信息进行利用匹配.匹配过程看下方代码即可，并不难:

KMP解题代码

class Solution {
public:
    int strStr(string haystack, string needle) 
    {   
        if(needle=="")
            return 0;
        
        //KMP
 
        int jump[needle.size()];
        jump[0]=-1;
        int k=-1;
        int i=0;
        //创建失效数组  abcabcd
        while(i<needle.size()-1)
        {
            if(k==-1 || needle[i]==needle[k])
            {
                i++;
                k++;
                
                if(needle[i]!=needle[k])
                    jump[i]=k;
                else
                    jump[i]=jump[k];
            }
            else    //内置kmp
                k=jump[k];
        }
                
  
        
        int x=0;
        int y=0;
        while(x<haystack.size() && y<int(needle.size())) //注意这里int化！！！！！！看bug看了好久，size返回值是unsignedint
        {
            if(y==-1 ||haystack[x]==needle[y])
            {
                x++;
                y++;
            }
            else
               y=jump[y];
            
        }
        
        if(y==needle.size())
            return x-y;
        else
            return -1;
        
        
        
    }
};