如果是朴素做法 暴力循环

[字符串暴力循环] [c++]
1
2
3
4
5
6
7
8
9
10
s[N],p[N];
for(int i=1;i<=n;i++)
{
    bool flag =true;
    for(int j=1;j<=m;j++)
    {
        if s[i]!=p[i] flag=false;
        break
    }
}

我们发现匹配慢就是因为回溯的步骤太多了 所以要优化
代码不好理解 但是原理简单
首先得知道最长前缀和最长后缀怎么求
我们发现匹配慢就是因为回溯的步骤太多了

[升级算法] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;

const int N=10010，M=10010；

int n,m;
char p[N],s[M];
int ne[N];//定义next[N]概率性报错

int main()
{
    cin>>n>>p+1>>m>>s+1;  注意 都是从1开始存的 方便操作
    //求ne[N]过程 
    for(int i=2,j=0;i<=n;i++)   //ne[1]=0 第一个元素肯定最长相等前后缀为0
    {
        while(j&&p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i]=j;
    }
    //kmp匹配过程
    for(int i=1,j=0;i<=m;i++) 
    //从i=1开始从原字符串第一个字符遍历 试图与s[i]匹配的是p[j+1]
    {
        while(j&&s[i]!=p[j+1]) j=ne[j]; 
        //ne[j]是 字串下标j与j之前的元素 的最长相等前后缀
        // j=0则代表重新匹配 只要j不退回起点 且匹配不成功时 j回溯到ne[j] 此时子串j与j之前的元素是和原字符串相同的 继续比较i与j+1
        if(s[i]==p[j+1]) j++; 如果下一个相同 继续操作
        if(j==n) //如果完全符合
        {
            cout<<i-n;//输出匹配位置
            j=ne[j];
        }
    }

}

举个例子
下标 1 2 3 4 5 6 7 8
s= a b a b a b c
p= a b a b a b a b
i 1 2 3 4 5 6 7 8
j+1 1 2 3 4 5 6 7 8
ne[]=0 0 1 2 3 4 5 6

首先下标为1均是a 所以i++ j++
这么比较下去 当i=7时 不相等了
此时j=6 ne[6]=4 所以j回溯到4 j+1为5
s= a b a b a b c
p= a b a b a b a b
接着继续相同操作