KMP template - string matching

1. subject

Text string ：haystack
Pattern string （ Substring ）：needle
The meaning of the question is to judge whether the text string contains a pattern string , If yes, the first matching position is returned

2. solution

2.1 Violence ：

Double pointer , A point to the beginning of the text string , Start of a pointing pattern string
Time complexity ：O(mn)

class Solution {
    
public:
    int strStr(string haystack, string needle) {
    
        int len1=haystack.size(),len2=needle.size();
        if(len1==0&&len2==0)return 0;
       
        for(int i=0;i<len1;i++){
    
            bool flag=true;
            for(int j=0;j<len2;j++){
    
                if(i+j>=len1||haystack[i+j]!=needle[j]){
    
                    flag=false;
                    break;
                }
            }
            if(flag)return i;
            
        }
        return -1;
    }
};

2.2 KMP Algorithm ：

thought ： When there is a string mismatch , You can know a part of the text that has been matched before , You can use this information to avoid matching from scratch
next Array ： It's quite a prefix table , When the record text string does not match the pattern string , Where should the pattern string start matching . That is, when the current position matching fails , Find the matching position in the previous pattern string , And then rematch .

prefixes ： Record subscripts i Before （ Include i） In the string of , What is the length of the same Prefix suffix
eg. character string a The prefix of the longest face of is 0, character string aa The prefix of the longest face of is 1, character string aaa The prefix of the longest face of is 2
Prefix ： All consecutive substrings starting with the first character that do not contain the last character
suffix ： All consecutive substrings that do not contain the first character and end with the last character

Why use prefix table ？

When index=5 when , Pattern string (0,4] The longest equal prefix and suffix strings in the string are substrings aa, When index=5 If it does not match , Then jump to index=2 Continue to match where

Time complexity ：O(n+m）
Be careful next Arrays may have been used in some header file , There may be a mistake , It is suggested to call it ne

Templates

// s[] Is a text string ,p[] It's a pattern string ,n yes s The length of ,m yes p The length of 
// Find the pattern string Next Array ：
s=" "+s;//char s[N];cin>>s+1;
p=" "+p;//char p[N];cin>>p+1;
// Only from 2 Start , from 1 It matched at the beginning 
for (int i = 2, j = 0; i <= m; i ++ )
{
    
	// When j There is no return to the starting point 
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

//  matching 
for (int i = 1, j = 0; i <= n; i ++ )
{
    
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    // The match is successful 
    if (j == m)
    {
    
        j = ne[j];
        //  The logic of a successful match 
    }
}

Answer key

class Solution {
    
public:
    int strStr(string haystack, string needle) {
    
        int len1=haystack.size(),len2=needle.size();
        if(len1==0&&len2==0)return 0;
        vector<int>ne(len2+1,0);
        haystack=" "+haystack;
        needle=" "+needle;
        for(int i=2,j=0;i<=len2;i++){
    
            while(j&&needle[i]!=needle[j+1])j=ne[j];
            if(needle[i]==needle[j+1])j++;
            ne[i]=j;
        }
       
        for(int i=1,j=0;i<=len1;i++){
    
            while(j>0&&haystack[i]!=needle[j+1]){
    
                j=ne[j];
            }

            if(haystack[i]==needle[j+1])j++;

            if(j==len2){
    
                return i-len2;
            }
        }
        return -1;
    }
};