萌新求助,一直70
查看原帖
萌新求助,一直70
265813
有毒的牛肉干楼主2020/11/28 18:25

第11和13个点T掉了,求大佬们帮看一下

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

const int N = 1e6 + 7;
int Pi[N];//Pi为前缀函数
char ptr[N], str[N];
void get_pi(char* s,int n);//n为s长度
int main()
{
	scanf("%s%s", str, ptr);
	int n = strlen(str), m = strlen(ptr);
	int j = 0;
	get_pi(ptr,m);
	for (int i = 0; i < n; i++)
	{
		while (j > 0 && ptr[j] != str[i])
			j = Pi[j - 1];
		if (str[i] == ptr[j])
			j++;
		if (j == m)//匹配的长度为子串长度时
		{
			printf("%d\n", i - m + 1 + 1);//输出子串出现位置
			j = 0;//初始化j
			i = i - m + 1;//允许重叠
		}
	}
	for (int i = 0; i < m; i++)
		printf("%d ", Pi[i]);
	return 0;
}
void get_pi(char* s,int n)
{
	for (int i = 1; i < n; i++)
	{
		int j = Pi[i - 1];//初始j为i-1的最长前后缀相同子串长度(前缀子串的结束位置)
		while (j > 0 && s[j] != s[i])	//如果第一个子串结尾的下一个字符与第i个字符不同
			j = Pi[j - 1];//j往前推一次
		if (s[i] == s[j])
			j++;//Pi[i]=Pi[i-1]+1
		Pi[i] = j;
	}
}
2020/11/28 18:25
加载中...