本文共 1085 字，大约阅读时间需要 3 分钟。

题目链接:

题目描述

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

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

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

输入格式

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

第二行输入字符串P。

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

第四行输入字符串M。

输出格式

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

数据范围

1≤N≤10^4

输入样例

3

aba

5

ababa

输出样例

0 2

解题思路

题意:求出所有p串在s串出现的位置。

Accepted Code:

/*  * @Author: lzyws739307453  * @Language: C++  */#include 
   
    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;}
   

转载地址：http://rybtf.baihongyu.com/