🔰模式匹配

给定主串 S = "S1S2...Sn"和模式 T = ”t1t2...tn“ ，在S中寻找T的过程称模式匹配。如果匹配成功，返回T在S中的位置，如果匹配失败返回0.

假设串采用顺序存储结构，串的长度放在数组0号单元，串值从1号单元开始存放：

模式匹配问题的特点：

1、 算法的一次执行时间不容忽视：问题规模通常很大，常常需要在大量信息中进行匹配 2、 算法改进所得的积累效益不容忽视：模式匹配操作经常被调用，执行频率高。

🔸介绍两种匹配方法： 1️⃣： BF算法 2️⃣： KMP算法

1️⃣模式匹配—BF算法

基本思想🖌：

📝从主串的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，直到T中的字符全部比较完毕，则说明本趟匹配成功； 或S中字符全比较完，则说明匹配失败。

算法过程🖌：
STEP1: 在串S和串T中设比较的起始下标i和j；
STEP2: 循环直到S或T的所有字符均比较完；

• 2.1 如果S[i]==T[j],继续比较S和T的下一个字符；
• 2.2 否则，将i和j回溯，准备下一趟比较；
  STEP3: 如果T中所的字符都比较完，则匹配成功，返回匹配的起始比较下标：否则，匹配失败，返回0；

算法步骤🖌：
入口函数（主串、模式串、起始位置）

1. 两个变量，一个是主串下标i，一个是子串下标j
2. 在两下串中比较：如果相同，下标下移，否则退回

算法描述🖌：

// javascript
// 在S中寻找T的过程称模式匹配,S主串，T模式串
function Index_BF( S, T, pos){
    i = pos, j = 0, sl = S.length, tl = T.length; // j代表模式串位置 i、pos表示主串位置
    while (i < sl && j < tl) {
        if (S[i] == T[j]){
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 1;
        }
    }
    if (i >= tl){
        return i - tl;
    } else {
        return -1;
    }
}
console.log(Index_BF('abdefd','ab',0));

算法性能🖌：
设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：
👉情况1️⃣:最好情况，即不成功匹配都发生在串T的第1个字符。
设匹配成功发生在Si处，则i-1次不成功的匹配中共比较i-1次，第i次成功匹配，共比较m次，把以共花i-1+m次，所有匹配成功的可能情况共为n-m+1种，则时间复O（m + n）
👉情况2️⃣:最坏情况，不成功匹配都发生在串T的最后一个字符串
前i-1次，每次比较m次才确定失配，前i-1次共比较（i-1）*m次，总共比较（i-1）m + m次,刚时间复杂度为O(mn)

2️⃣模式匹配—KMP算法

KMP算法思想🖌
本算法是对BF算法思想的改进，每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用已得到的”部分匹配“结果将模式串向右滑尽可能远的一段距离，继续进行比较。
定义next[j]函数，表明当前模式中第j个字符与主串中相应字符”失配“时，在模式串中需要重新和主串中该字符进行比较的字符位置。

1. 小结1️⃣: next[j]函数的意义
   next[j]函数表征着模式串p中最大的相同首字串和尾子串（真子串）的长度。可见模式串中相似部分越多，则next[j]函数越大，它既表示模式串中的字符之间的相关度越高，模式串向右滑动的越远，与主串进行比较的次数越少，时间复杂度越低。
2. 小结2️⃣: 回溯模式串也就是子串
   第一，主串中的i可以不回溯，模式串向右滑动到新的比较起点k，并且k仅与模式串p（模式串）T有关。 第二，注意两个问题，
   问题1：如何由当前部分匹配结果，确定模式串向右滑动的新比较起点K？
   问题2：模式串应该向右滑动多远才是最高效率的？
3. 计算next[j]的方法
   🔖情形1：
   当j=1时，next[j]=0;
   next[j]=0表示不进行字符串比较
   🔖情形2：
   当j>1时，next[j]的值为：
   模式串的位置从1到j-1构成的串中所出现的首尾相同的子串的最大长度为1。
   🔖情形3：
   若无首尾相同的子串next[j]的值为1。
   next[j]=1表示模式串从头部开始比较

KMP算法描述🖌

// javascript的kmp算法
    let next = [];
    let s='acabaabaabcacaabc';
    let t='abaabcac';
    function index_KMP( S, T, pos){
        i = pos,j = 0, sl = S.length, tl = T.length; // j代表模式串位置 i、pos表示主串位置
        while (i < sl && j < tl){
            if(S[i] == T[j]){
                i++;
                j++;
            } else if(j == 0){
                i++;
            }else{
                j = next[j-1]; // 模式串指针往回滑
            }
        }
        
        if( j >= tl){
            return i-tl;
        } else {
            return 0;
        }
    }

    /**
     * 存放对比失败后跳转的位置
     * */
    function get_next( T ){
        i = 1;
        next[0] = 0; j = 0 ;
        while( i < T.length){
            if (T[i] == T[j]){ // 如果相等，指针向后移。 i指针不断后移，j指针总是只向最大不相等字符的下一个
                j++;
                next[i] = j;
                ++i;
            }else if(j==0){
                next[i] = j;
                ++i;
            } else {
                j = next[j]; // 回溯要跳转的位置
            }
        }
    }
    get_next(t);
    console.log(index_KMP(s,t,0));

KMP算法练习🖌:
设目标子串 S="aaabaaaab" 模式串T=“aaaab”，S的长度n=9,T的长度m=5。用指针i表示目标串S的当前比较字符位置，用j表示模式串T的当前比较位置，KMP比较过程如下

j	1	2	3	4	5
T[j]模式	a	a	a	a	b
next[j]	0	1	2	3	4

在主串S="aaabaaaab"模式串T=“aaab”匹配时，当i=4，j=4时，S.data[4]<>T.data[4],此是next[j]还需进行i=4、j=3，i=4、j=2，i=4、j=1,这样三次比较我们会发现，模式串中前4个字符是相等的，因些不需要和主串的第四个字符进行比较，直接进行i=5、j=1时的字符比较。因此可以如下图

j	1	2	3	4	5
T[j]模式	a	a	a	a	b
next[j]=k	0	1	2	3	4
nextVal[j]	0	0	0	0	4

小结：比较T.data[j]和T.data[k],若不等，则nextVal[j]=next[j],若相等，nextVal[j]=nextVal[k]

KMP算法的时间复杂度🖌
设主串S长度为n，模式串T长度为m，在KMP算法中next数组的时间复杂度为O（m），在后面的匹配中因S的下标不减所以不回溯，比较次数可记为n，所以KMP算法总的时间复杂度为O（m+n)