「LOJ#10036」「一本通 2.1 练习 2」Seek the Name, Seek the Fame （Hash

 1 编号     题目     状态     分数     总时间     内存     代码 / 答案文件     提交者     提交时间
 2 #229879     #10036. 「一本通 2.1 练习 2」Seek the Name, Seek the Fame    Accepted     100     237 ms     6908 KiB     C++ / 913 B     qwerta     2018-10-15 19:03:34
 3 
 4 #include<iostream>
 5 #include<cstring>
 6 #include<cstdio>
 7 using namespace std;
 8 #define ULL unsigned long long
 9 char s[400003];
10 ULL h[400003];
11 const int p=33;//每位乘上的数（总感觉只乘26是活等着被卡
12 ULL ep[400003];
13 int main()
14 {
15     //freopen("a.in","r",stdin);
16     ios::sync_with_stdio(false);
17     cin.tie(false),cout.tie(false);
18     while(cin>>s)
19     {
20         int n=strlen(s)-1;
21         for(int i=0;i<=n;++i)
22         {
23           h[i]=h[i-1]*p+s[i]-‘a‘+1;//算Hash前缀和
24           //cout<<h[i]<<" ";
25         }
26         //cout<<endl;
27         ep[0]=1;
28         for(int i=1;i<=n;++i)
29         {
30           ep[i]=ep[i-1]*p;//算p的次方
31           //cout<<ep[i]<<" ";
32         }
33         //cout<<endl;
34         for(int i=0;i<=n;++i)
35         {
36             ULL ha,hb;//设ha为前缀，hb为后缀
37             ha=h[i];
38             hb=h[n]-h[n-i-1]*ep[i+1];
39             //cout<<ha<<" "<<hb<<endl;
40             if(ha==hb){cout<<i+1<<" ";}
41         }
42         cout<<endl;
43     }
44     return 0;
45 }