KMP idea and template code

Refer to the post ：https://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html
video ：https://www.acwing.com/video/259/
Example ：https://www.acwing.com/problem/content/833/

BF Algorithm （ violence ）

thought

BF Algorithm is violent solution , Double cycle , If there is a character mismatch, go back （i=i-j+1）

Code

int BFMatch(char *s,char *p)
{
    
    int i,j;
    i=0;
    while(i<strlen(s))
    {
    
        j=0;
        while(s[i]==p[j]&&j<strlen(p))
        {
    
            i++;
            j++;
        }
        if(j==strlen(p))
            return i-strlen(p);
        i=i-j+1;                // The pointer i to flash back 
    }
    return -1;    
}

KMP

thought

KMP The algorithm mainly solves optimization BF Algorithm ,BF When the fifth time in the algorithm does not match , The sixth time j Can be directly from 2 Start , No need to 0 Start , This redundant matching process occurs in kmp It's cancelled .kmp No more i=i-j+1 Pointer backtracking process of , Just think about it every time j Just a pointer

next Array idea

Using the idea that the largest suffix is equal to the prefix
First of all, let's know what prefix is , What is a suffix .
With abacab For example
Prefix ：a``ab``aba``abac``abaca
suffix ：b``ab``cab``acab``bacab
It can be seen that the pre suffix does not include itself , among The largest suffix is equal to the prefix Means the longest equal prefix , In this case, yes ab

Code

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    
    cin >> n >> p + 1 >> m >> s + 1;

    //  solve next Array 
    //  because j=0 It's empty. ,j=1 It's the first number ,ne[1]=0, therefore j from 2 Start 
    for (int j = 2, k = 0; j <= n; j ++ )
    {
    
        //  If it doesn't match, keep going backwards . There is no retreat （k!=0）
        while (k!=0 && p[j] != p[k + 1]) k = ne[k];
        if (p[j] == p[k + 1]) k ++ ;
        ne[j] = k;
    }
    
    //  matching 
    for (int i = 1, j = 0; i <= m; i ++ )
    {
    
        //  If it doesn't match, keep going backwards . There is no retreat （j!=0）
        while (j!=0 && s[i] != p[j + 1]) j = ne[j];
        //  If the match is successful, look at the next  
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
    
            j = ne[j];
            //  The logic of a successful match 
            printf("%d ", i - n);
        }
    }

    return 0;
}