KMP算法（题目）

A. 子串位置

题目描述：

给定一个父字符串 s 和子字符串 p ，请按照从前向后的顺序，请求出 p 在 s 中所有出现的起始位置。

例如：s=ABADABCEABABA，p=ABA，则求解的结果是：1 9 11 。

输入：

第 1 行读入一个仅包含大写字母的字符串 s；

第 2 行读入一个仅包含大写字母的字符串 p ；

s 和 p 均是长度不超过 106 的字符串。

输出：

输出 1 行，按题意输出 p 在 s 中出现的位置，数字之间用空格隔开。

样例：

输入：

ABADABCEABABA
ABA

输出：

1 9 11

代码如下:

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
char s[N],p[N];
//ne：存储p字符串前i个字符的最大前缀和后缀相同的长度
int ne[N];
int main(){
    scanf("%s%s",s+1,p+1);
    //计算ne数组
    ne[0] = ne[1] = 0;
    int lens = strlen(s+1),lent = strlen(p+1);
    for(int i = 1,j = 0;i < lent;i++){
        while(j && p[i+1]!=p[j+1]) j = ne[j];
        if(p[i+1] == p[j+1]) j++;
        ne[i+1] = j;
    }

    //尝试匹配父子字符串
    for(int i = 0,j = 0;i < lens;i++){
        while(j && s[i+1] != p[j+1]) j = ne[j];
        if(s[i+1] == p[j+1]) j++;
        //配对成功，输出起始位置
        if(j == lent){
            printf("%d ",i + 1 - lent + 1);
            j = ne[j];
        }
    }
    return 0;
}

B. 最多子串重复次数

题目描述：

给定若干个长度≤106 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有 3 个 ab 连接而成。

输入：

输入若干行（所有行的字符串的长度之和≤107），每行有一个字符串，字符串仅含英语小写字母。特别的，字符串可能为 . 即一个半角句号，此时输入结束。

输出：

对于每行输入，输出一个整数，代表计算的结果。

样例：

输入：

abcd
aaaa
ababab
.

输出：

1
4
3

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N];
int ne[N]; 
int main(){
	while(scanf("%s",s+1)&&s[1]!='.'){
		ne[0]=ne[1]=0;
		int len=strlen(s+1);
		for(int i=1,j=0;i<len;i++){
			while(j&&s[i+1]!=s[j+1]) j=ne[j];
			if(s[i+1]==s[j+1]) j++;
			ne[i+1]=j;
		}
		if(len%(len-ne[len])==0) printf("%d\n",len/(len-ne[len]));
		else printf("%d\n",1);
	}
	return 0;
}

C. 前缀和后缀

题目描述

给定若干由小写字母组成的字符串（这些字符串总长 ≤4×105 ），在每个字符串中求出所有既是前缀又是后缀的子串长度。

例如：ababcababababcabab，既是前缀又是后缀的：

ab，abab，ababcabab，ababcababababcabab 。

输入：

输入若干行，每行一个字符串。

输出：

对于每个字符串，输出一行，包含若干个递增的整数，表示所有既是前缀又是后缀的子串长度。

样例：

输入：

ababcababababcabab
aaaaa

输出：

2 4 9 18
1 2 3 4 5

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
char s[N];
int ne[N];
stack<int> st;

int main(){
    while(scanf("%s",s+1) != EOF){
        //计算s字符串的next数组
        ne[0] = ne[1] = 0;
        int len = strlen(s+1);
        for(int i = 1,j = 0;i < len;i++){
            while(j && s[i+1] != s[j+1]) j = ne[j];
            if(s[i+1] == s[j+1]) j++;
            ne[i+1] = j;
        }

        //计算字符串s前缀和后缀相等的情况
        st.push(len);
        while(ne[len] != 0){
            st.push(ne[len]);
            len = ne[len];
        }

        //输出
        while(!st.empty()){
            printf("%d ",st.top());
            st.pop();
        }
        printf("\n");
    }
    return 0;
}