【集训DAY15】好名字【hash】

思路：

直接一个hash判断是否出现就行了

$code$

#include<iostream>
#include<cstdio>
#include<cstring>

typedef unsigned long long ull;

using namespace std;

ull pow[400010], has[400010], mod = 127;
char s[400010];

int main() {
    
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	pow[0] = 1;
	for(int i = 1; i <= n; i ++) pow[i] = pow[i - 1] * mod, has[i] = has[i - 1] * mod + ull(s[i] - 'A' + 1);
	for(int i = 1; i <= n; i ++) {
    
		ull ha = has[n] - has[n - i] * pow[i];
		if(ha == has[i] && ha != 0) printf("%d ", i);
	}
	return 0;
}