模拟匹配法

程序优化

• 1.固定i的位置
• 2.匹配失败时待匹配数组尽量向右挪动

情景模拟

• 文本串: BBC_ABCDAB_ABCDABCDABDE
• 模式串: ABCDABD
• 匹配失败时，希望向右跳的尽量远

i = 4 , j = 6 时，s[i+j] 与 p[j]匹配失败
BBC_ ABCDABABCDABCDABDE
ABCDABD
BBC ABCDAB_**
最多 ABCDABD
找到匹配失败时最远移动距离的位置，并记录
如果还是匹配不成功，则继续向左跳转
next[i]表示以第i个字符结尾时的最长前后缀相等部分的长度
（不做偏移）

next数组

• next数组用来记录匹配失败时需要跳转到的下一个位置
• 匹配思路

对于模式串P，递推求解next:
1.如果P[next[i-1]==P[i],则有next[i]=next[i-1]+1。
2.如果P[next[i-1]] \ne P[i]
令 j = next[i-1]
不断比较P[j]和P[i],不相同则令j=next[j-1],直到P[j]=P[i]或者j=0。

相当于

• 文本串: ABCDABD

• 模式串: ABCDABD

• 字符串 A B C D A B D

• 下标 0 1 2 3 4 5 6

• next数组 ：

• 初始化 next[0] = 0

• 自己和自己匹配

• next数组用来记录匹配失败时需要跳转到的下一个位置

• 匹配思路

• 1.最外层的i固定从头到尾移动

• 2.如果当前的p[i]==p[j]，则让j++

• 3.如果当前的p[i]!=p[j]，则让整个p串继续向右移动，同样也是跳到尽可能远的位置（相当于j向左移动）

• 4.设置next[i] = j

模板代码

#include <iostream>
#include <cstring>

const int N = 1000000 + 5000;

char ch1[N];
char ch2[N];

int len1,len2;

int next[N];

long long ans = 0;

void get_next(char* ch2)
{
    int j = 0;
    for (int i = 1 ; i < len2 ; i ++)
    {
        while (j != 0 && ch2[i] != ch2[j])
        {
            j = next[j - 1];
        }
        if (ch2[i] == ch2[j]) j ++;
        next[i] = j;
    }
}

void kmp(char* ch1,char* ch2)
{
    int j = 0;
    for (int i = 0 ; i < len1 ; i ++)
    {
        while (j != 0 && ch1[i] != ch2[j])
        {
            j = next[j - 1];
        }
        if (ch1[i] == ch2[j])
        {
            j ++;
        }
        if (j == len2)//匹配成功 
        {
            ans ++;
            j = next[j - 1];
        }
    }
}

int main()
{
    std :: cin >> ch1 >> ch2;
    len1 = strlen(ch1);
    len2 = strlen(ch2);
    get_next(ch2);
    kmp(ch1,ch2);
    std :: cout << ans;
}