P3375 【Template] KMP string matching

Title Description

As the title, give two strings S1 and s2, where S2 is a substring of s1, find out all the positions of S2 in s1.

In order to reduce the situation of cheating, next output the prefix array next of the substring.

（If you don’t know what that means, don’t ask, go to Baidu and learn about the KMP algorithm.

Input output format

Input format:

The first behavior is a string, that is S1.

Second behavior a string, that is S2

Output format:

A number of rows, each containing an integer, indicating the position of S2 in S1.

The next 1 lines, including length (S2), represent the value of the prefix array next[i].

Examples of input and output

ABABABC
ABA

1
3
0 0 1 

Explain

Time and space constraints: 1000ms, 128M

Data size:

Set S1 length to N and S2 to M

For 30% data: N< =15, M< =5

For 70% data: N< =10000, M< =100

For 100% data: N< =1000000, M< =1000000

Example shows:

So the two matching positions are 1 and 3, output 1, 3.

KMP

next[i] Represents the strict longest prefix corresponding to the suffix length.

#include<cstdio>
#include<iostream>
#include<cstring>

#define N 15000000
using namespace std;

char s[N],t[N];
int next[N],l,L,j;

void KMP() {
    for(int i=1,j=0; i<L; i++) {
        while(j&&t[i]!=t[j]) j=next[j];
        if(t[i]==t[j]) j++;
        next[i+1]=j;
    }
}

int main() {
    cin>>s;
    l=strlen(s);
    cin>>t;
    L=strlen(t);
    KMP();
    for(int i=0,j=0; i<l; i++) {
        while(j&&s[i]!=t[j]) j=next[j];
        if(s[i]==t[j]) ++j;
        if(j==L) printf("%d\n",i-L+2);
    }
    for(int i=1; i<=L; i++) printf("%d ",next[i]);
    return 0;
}