poj3461 http://poj.org/problem?id=3461 字符串hash模板题。给你2个串s1,s2(长度n,m),问s1在s2中出现几次。 字符串hash步骤： 1、  取一个质数p 我一般取999983。据说应该再模一个q(一般取1e9+7),但模了有时会超时。于是我一般不模q，让它自然溢出。但有一种数据专门卡这种自然溢出，于是我写一种假的双hash：将q作为另一个p，再做一遍。 2、  预处理p^(1~m) 3、  类似前缀和方式求出s2的hash[i]：h[i]=h[i-1]*p+s2[i] 4、  求出s1的哈希值s 5、  求出s2长度为n的子串的哈希值h[i+n]-h[i]*(p^n),并与s比较 #include #include #include #include #define p 999983 #define q 1000000007 #define ull unsigned long long using namespace std; ull h[1000001],h2[1000001],po[1000001],qo[1000001]; char s1[10001],s2[1000001]; int main() { int t; scanf("%d",&t); po[0]=1; qo[0]=1; for(int i=1;i<1000000;++i) po[i]=po[i-1]*p, qo[i]=qo[i-1]*q; while(t--){ scanf("%s%s",s1+1,s2+1); int n=strlen(s1+1),m=strlen(s2+1); for(int i=1;i<=m;++i){ h[i]=h[i-1]*p+s2[i], h2[i]=h2[i-1]*q+s2[i]; //cout<