831. KMP string

Given a pattern string S, And a template string P, All strings contain only uppercase and lowercase letters and Arabic numerals .

Template string P In mode string S Appears as a substring many times in .

Find the template string P In mode string S The starting subscript of all positions appearing in .

Input format
Enter the integer in the first line N, Representation string P The length of .

The second line of input string P.

In the third line, enter the integer M, Representation string S The length of .

On the fourth line, enter the string S.

Output format
All in one line , Output the starting subscript of all occurrences （ Subscript from 0 Start counting ）, Integers are separated by spaces .

Data range
1≤N≤105
1≤M≤106
sample input ：
3
aba
5
ababa
sample output ：
0 2

/** The string subscript of the following code is from 1 Start **/
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 1000010;

char S[M], T[N];// Main string and mode string 

int ne[N];// Pattern string next Array 
int n, m;


/** Method 1 ：brute-force The brute force algorithm   Simple pattern matching algorithm */
int normalMatch(char* S, char* T, int pos)
{
    
    int i = pos;
    int j = 1;

    while(i <= m && j <= n)
    {
    
        if(S[i] == T[j])// If the match ,i and j Move backward 
            i++,j++;
        else
            i = i-j+2, j = 1;// If it doesn't match ,i Go back to i The next position at the beginning ,j Go back to 1
    }
    if(j > n) return i - n;
    return 0;
}

/**  Method 2 ：  Calculate the of the pattern string next Array time , i Subscript for the current character , Just focus on the pattern string  1~i-1  The length of the equal maximum true pre suffix in the position is sufficient  next[i] =  The length of the maximum true pre suffix  + 1;  Be careful C++ It doesn't work inside char Storage int Type value ,char The storage range of is -128~127  Rewrite the   Yan Weimin version 《 data structure 》kmp obtain next Array code , Easy to understand  **/
void get_next(char* T)
{
    
    int i, j;
    ne[1] = 0;// At the first position of the pattern string next The value is 0, The tag can no longer be traced 
    for(i = 2; i <= n; i++)// Calculate from the second position next value 
    {
    
        j = ne[i-1];// First of all, will j Set as  i The previous position will be traced back to the position 
        while(j && T[i-1] != T[j])// When j You can go back to , also T[i-1] When comparing with characters that need to be traced back , If it doesn't match , be j Keep going back 
            j = ne[j];
        ne[i] = j+1;//j When the mode string is i When the position does not match , Subscript that requires backtracking , Also just equal to the length of the maximum true pre suffix  next[i] =  The length of the maximum true pre suffix  + 1;
    }
}

/** Yan Weimin version 《 data structure 》kmp Matching process */
//S Main string  T For the pattern string  pos Subscript for starting query 
int kmp(char* S, char* T, int pos)
{
    
    int i, j;
    i = pos;// Master string slave pos Start 
    j = 1;// Mode string slave 1 Start 

    while(i <= m && j <= n)
    {
    
        if(j == 0 || S[i] == T[j])// If j Back to 0  perhaps   The character of the position to which the pattern string is traced   And   Main string current character   matching , i and j Then move back 
            i++, j++;
        else
            j = ne[j];// If the pattern string is traced back to the position of the character   And   Main string current character   Mismatch ,  be j Go back to next[j]
    }

    if(j > n)// After matching , If the match is successful , that j It will arrive  T[0]+1 i It will also go to a position behind the completion of matching 
        return i - n;
    return 0;
}




int main()
{
    
    cin>> n >> T+1 >> m >> S+1;

// get_next(T);
//
// // The range of subject data is relatively strict , Will timeout 
// for(int i = 1; i <= m; i++)
// {
    
// int tmp = kmp(S,T,i);
// if(tmp == 0)
// break;
// else
// i = tmp;
// cout<<tmp-1<<' ';
// }

    /** Method 3 ： Note that this method of calculation next The result of array and Yan Weimin version 《 data structure 》 obtain next The result of the array is different **/
    /** obtain next Array ,i from 2 Start **/
    ne[1] = 0;                       // Subscript to be 1 The character corresponding to next The array value is fixed to 0
    int i, j;
    for(i = 2, j = 0; i <= n; i++)   // Traversing pattern strings , From the subscript for 2 Start calculating next value 
    {
    
        while(j && T[i] != T[j+1])    // If j Not for 0  And will i Follow j+1 Match the characters of the position , Be able to match successful situations , Must be based on i Is the suffix at the end , Follow with j+1 Successfully matched the prefix at the end , This pre suffix must be the largest true pre suffix , Because the pre suffix is judged one by one from the beginning to the end of the string 
            j = ne[j];                // If i Follow j+1 The characters of the position do not match , be j Keep going back , Every time you go back , Just compare once i Follow j+1 Whether the characters of the position match 
        if(T[i] == T[j+1]) j++;       // If j by 0  also   At present i The character of the position does not match the first character , be j Always for 0; If i Follow j+1 Character matching of position , Then the length of the character before the suffix increases , That is, the subscript of the character indicated by the pattern string j Self increasing 
        ne[i] = j;                    // Will the current i Subscript that requires backtracking j Assign to the current next Array 
    }

    /**kmp Matching process ,i from 1 Start **/
    for(i = 1, j = 0; i <= m; i++)
    {
    
        while(j && S[i] != T[j+1])// When the main string i The position follows the pattern string j+1 When the position characters do not match , Pattern string j Keep going back , until j Go back to the subscript 0( The previous position of the first character )  perhaps   Trace back to the position where the maximum prefix and suffix match exactly 
            j = ne[j];
        if(S[i] == T[j+1]) j++;   // If the main string i The position follows the pattern string j+1 Position matching , That is, when the maximum true pre suffix matches ,j Move a position back ,i It will also move back a position in the cycle , Then the next cycle continues to judge the next i Follow j+1 match 
        if(j == n)                // Get to this point , Fixed time j+1 Follow i Position character matching , also j The last character of the pattern string has been reached 
        {
    
            cout<<i-n<<' ';      // Because the title is output subscript 0 Start , So it's output  i- Mode string length 
            j = ne[j];           // When the primary main string and pattern string are matched ,i because for The loop must move to the next character that exactly matches the pattern string 
                                 //j It was originally in the last character of the pattern string , take j The assignment is ne[j], The purpose is to continue to judge in the next cycle   With i-1 The next character of the string with the suffix at the end   Follow or not   With ne[j] Match the next character of the prefix at the end 
        }
     }

    return 0;
}