AcWing - KMP字符串(KMP)

题目链接:https://www.acwing.com/problem/content/description/833/
时/空限制： 1s / 64MB

题目描述

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式

第一行输入整数N，表示字符串P的长度。

第二行输入字符串P。

第三行输入整数M，表示字符串S的长度。

第四行输入字符串M。

输出格式

共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

数据范围

输入样例

3
aba
5
ababa

输出样例

0 2

解题思路

题意:求出所有p串在s串出现的位置。
思路:直接利用KMP算法。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 5;
const int MAXM = 1e5 + 5;
int nex[MAXN];
char p[MAXN], s[MAXM];
void Get_Next(char str[], int len) {
    int i = 0, j = -1;
    nex[0] = -1;
    while (i < len) {
        if (~j && str[i] != str[j])
            j = nex[j];
        else nex[++i] = ++j;
    }
}
void KMP(char sa[], int la, char sb[], int lb) {
    Get_Next(sb, lb);
    int i = 0, j = 0;
    while (i < la) {
        if (~j && sa[i] != sb[j])
            j = nex[j];
        else i++, j++;
        if (j >= lb) {
            j = nex[j];
            printf("%d ", i - lb);
        }
    }
}
int main() {
    int n, m;
    scanf("%d%s%d%s", &n, p, &m, s);
    KMP(s, m, p, n);
    printf("\n");
    return 0;
}