String Search

题目：给定两个字符串A、B，判断B在A中是否存在，存在返回A中的下标，不存在返回-1；

例：
A:ABCABCAABCABCD

B:ABCABCD
返回值：7

注意：在面试题如果遇到这个问题，考察indexof整体是怎么实现的。

本道题可以使用hash算法，但要将字符全部放进hash表，会造成时间复杂度的上升。

解答

BF：暴力算法

逐字符的进行匹配，比较两个字符串，如果当前字符匹配成功，就匹配下一个字符，如果失败，i回溯，j归0；

时间复杂度O(m*n),与主串和匹配的串的长度都正相关

int search(String pat,String txt){
       int M = pat.length();
       int N = txt.length();
       for (int i=0;i<=N-M;i++){
           int j;
           for (j=0;j<M;j++){
               if (pat[j]!=txt[i+j]){
                   break;
               }
           }
           //pat全部匹配了
           if (j==M) return i;
       }
       return -1;
   }

BK:hash算法

基于BF进行优化，将A中字符按照顺序和B串的长度进行截取，abc，bcd，cde，def，efg。hash运算然后与B的hash值进行比较。

时间复杂度：O(M*N)，hash算法参与的字符位数（模式串的长度）、及主串长度正相关

优化：hash算法：按照26进制取和，abc = 1+2+3=6

则每一个子串的hash值是前一个子串的hash值减去子串最小下标值、加上本串的最大下标值

bcd = abc-a+d=6-1+4=9

据此时间复杂度变为O（N），只与主串长度有关，但是hash冲突极端情况下会退化为BF

BM算法

坏字符规则：从右往左匹配，找到A中第一个不匹配的字符(坏字符)，将B串右移、直到B串出现与A串坏字符对齐的字符，再从右往左寻找坏字符。如果B串中没有该坏字符、则直接移到下一位即可。

好后缀规则：从右往左匹配，找到坏字符(意味看该坏字符后面的串是匹配的，该串即为好后缀)，往左寻找B中是否还有该好后缀，如果有、将B右移到该位置与A好后缀对齐。重复该规则。如果B串往右没有该好后缀，则右移到好后缀的往右错一位的位置，重复该规则。避免B串的前缀与好后缀的后缀匹配

两种规则综合使用，哪种移动的位数多使用哪种

时间复杂度: 0(n/m)， 最坏O(m*n)