AcWing 4183. 前后缀字符串
原题链接
简单
作者:
tobequiet
,
2025-02-04 22:15:02
,
所有人可见
,
阅读 2
#include<iostream>
#include<cstdio>
#include<cstring>
int const N = 4e5 + 10, P = 131;
char str[N];
typedef unsigned long long ULL;
ULL h[N],p[N];
ULL get(int l,int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
int main(){
p[0] = 1;
h[0] = 0;// 写不写都行啊,因为我从1开始遍历,全局变量的话h[0]自动就是0
while(scanf("%s",str+1) != EOF){
int len = strlen(str + 1);
for(int i = 1; i <= len; i++){
p[i] = p[i-1] * P;
h[i] = h[i-1] * P + str[i];
}
for(int i = 1;i <= len; i++){//这个循环,get函数比较时,两个参数是一定的1和len,但是还有两个是变化的,但用一个变量就可以,因此是一层循环
int l1 = 1;
int r1 = i;
int l2 = 1 + len - i;
int r2 = len;
if(get(l1,r1) == get(l2,r2)){
printf("%d ",i);
}
}
printf("\n");
}
return 0;
}