一本通 1458：Seek the Name, Seek the Fame

给定若干字符串（这些字符串总长 ≤4×10⁵​​ ），在每个字符串中求出所有既是前缀又是后缀的子串长度。

这题应该用kmp. 但这里记一下字符串哈希

#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 typedef unsigned long long ll;
  const int N=1e6+5;
 char s[N];
 
 ll n;
 ll h[N],pow[N];
 ll bas=131;
 
 void HASH(char *s){
     h[0]=0;
      n=strlen(s+1);
     for(int i=1;i<=n;i++){
         h[i]=h[i-1]*bas+s[i];
     }
 }
 int main(){
     int i;
     pow[0]=1;
     for(i=1;i<=1e6;i++) pow[i]=pow[i-1]*bas;
     while(cin>>s+1){
         HASH(s);
         for(i=1;i<=n;i++){
             if(h[i]==h[n]-h[n-i]*pow[i]) cout<<i<<' ';
         }
         cout<<endl;
     }
       
 }