第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;
}
}