String （套路Hash）
题目链接：https://vjudge.net/contest/344930#problem/I
题目大意：给你一个串s,和m,l.问你有多少长度为m*l的s的子串满足该子串由m个长度为l且个不相同的子串组成的个数.问的是长度为m * l的子串的个数。
思路：首先预处理出所有长度为l的字串的Hash值，之后有点像滑动窗口，前面减少了一个那么后面就增加一个。这样就可以避免算法的复杂度成为O(n^2)
1 #include <stdio.h> 2 #include <algorithm> 3 #include <iostream> 4 #include <stdlib.h> 5 #include <string> 6 #include <string.h> 7 #include <math.h> 8 #include <vector> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 14 15 #define INF 0x3f3f3f3f 16 #define LL long long 17 18 typedef unsigned long long ull; 19 const int maxn = 2e5+10; 20 21 22 char s[maxn]; 23 ull base = 131; 24 ull p[maxn],h[maxn]; 25 26 std::map<ull,int > mp; 27 28 ull get(int l,int r){ 29 return (h[r] - h[l-1]*p[r-l+1]); 30 } 31 32 int main() { 33 p[0] = 1; 34 for (int i=1;i<maxn;i++) { 35 p[i] = p[i-1] * base; 36 } 37 int m,l; 38 while (~scanf("%d%d",&m,&l)) { 39 scanf("%s",s+1); 40 int len = strlen(s+1); 41 int ans = 0; 42 for (int i=1;i<=len;i++) { 43 h[i] = h[i-1] * base + s[i]; 44 } 45 for (int i=1;i<=l && i+m*l-1<=len;i++) { //枚举长度 46 mp.clear(); 47 for (int j=i;j<=i+m*l-1;j+=l) { // 枚举i+m*l-1之前的长度为l的Hash 48 ull temp = get(j,j+l-1); 49 mp[temp]++; 50 } 51 if (mp.size() == m) { 52 ans++; 53 } 54 for (int j=i+m*l;l+j-1<=len;j+=l) { //枚举i+m*l-1之后的长度为l的Hash 55 ull temp = get(j-m*l,l+j-m*l-1); 56 mp[temp]--; // 前面减少一个 57 if (mp[temp] == 0) 58 mp.erase(temp); 59 temp = get(j,j+l-1); // 后面增加一个 60 ++mp[temp]; 61 if (mp.size() == m) 62 ans++; 63 } 64 } 65 printf("%d\n",ans); 66 } 67 return 0; 68 }