字符串哈希
字符串哈希就是将一个字符串映射为一个整数，该整数就可以用于vis标记有没有出现过，就不用遍历所有字符串了。
哈希公式：
hash[i] = hash[ i - 1 ] *p + id( s[i] )
其中id（x）为x-‘a’+1或者x的ask码，p为质数。例如对abcd哈希： 
可以看到，在求abcd的过程，也顺便把abcd前缀的哈希值求了一遍，那么现在如果要获得abcd子串的哈希值呢，例如要获得bc的哈希值，要从b开始哈希一遍吗？其实是有o（1）的算法的：
来看看 abcd 如果从1开始标号，s[1]=a,s[2]=b,s[3]=c,s[4]=d,为推导方便省略id（），那么：
hash [1]=s[1];
hash [2]=s[1]*p+s[2]
hash [3]=s[1]*p2+s[2]*p+s[3]
hash [4]=s[1]*p3+s[2]*p2+s[3]*p+s[4]
现在要求s2s3的哈希值，根据定义就是s[2]*p+s[3],现在观察一下上面四条式子，很容易看出hash[ 3 ]- hash[ 1 ]*p2就等于hash[s2s3]了。
可以推广出公式：在字符串s中，第l到r位子串的哈希值为：hash[r]-hash[l-1]*pr-l+1,所以，只要我们得到了一个字符串的哈希值，就可以在o(1)的时间内得到它的子串的哈希值。
例题
华工赛字符串题：https://ac.nowcoder.com/acm/contest/625/K
意思是给定一个字符串，有q次查询，每次查询给字符串设个断点，计算断点前的字符串的子串在断点后的字符串出现的次数和。
例如ababa，对于查询给出的2，将它分成了ab aba两段，前面的子串有a,b,ab, 在后面分别出现了2,1,1次，所以答案是4。字符串长度是1000，而查询有1e5那么多，肯定要预处理ans数组的。总体思路为：
ac代码：
1 #include<bits/stdc++.h> 2 #include<tr1/unordered_map> 3 using namespace std::tr1; 4 #define ll long long 5 #define maxn 1234 6 ll t,seed=131,ans[maxn]; 7 ll f[maxn],g[maxn],sum,x;//f【i】为前i个字母组成的前缀哈希成的数字 8 unordered_map<ll,int>pre,now; 9 char s[maxn]; 10 ll geth(int l,int r) 11 { 12 return f[r]-f[l-1]*g[r-l+1]; 13 } 14 int main() 15 { 16 scanf("%s%lld",s+1,&t);//输入字符串,从一开始 17 int n=strlen(s+1);//长度为n 18 g[0]=1;//....................... 19 for(int i=1; i<=n; i++) 20 {//................ 21 g[i]=g[i-1]*seed;//g用于求子串的哈希值 22 f[i]=f[i-1]*seed+s[i];//将每个前缀哈希成一个数字（fi是ll） 23 } 24 for(int i=1; i<=n; i++) 25 for(int j=i; j<=n; j++) 26 pre[geth(i,j)]++;//i到j为一条子串，并将该子串哈希，放到pre里面，个数++ 27 for(int i=1; i<=n; i++) 28 {//从一开始设置断点 29 for(int j=i; j>=1; j--) 30 { 31 ll id=geth(j,i);//获得前件后缀的哈希值 32 now[id]++;//当前后缀的个数++ 33 if(pre[id])//若后件有该子串，sum+上该子串的个数 34 sum+=pre[id]; 35 }; 36 for(int j=i; j<=n; j++) 37 { 38 ll id=geth(i,j);//获取后件子串的哈希值 39 pre[id]--;//子串个数-- 40 if(now[id]) 41 sum-=now[id]; 42 } 43 ans[i]=sum;//对此时的断点预处理完成 大重点，sum没有初始化，是继续用的 44 } 45 while(t--) 46 { 47 scanf("%lld",&x); 48 printf("%lld ",ans[x]); 49 } 50 return 0; 51 }