原文出处：http://www.cnblogs.com/Norlan/p/4886383.html 写的超好
http://acm.hdu.edu.cn/showproblem.php?pid=4821
这是2013年长春区域赛的铜牌题。。。然而第一次做的时候一直觉得会超时的。。最后才知道并没有想象中的那么恐怖；
这题有两个注意的地方：
(1)h[i] = h[i-1] * seed + s[i] - 'a' + 1;防止ab和aab的hash值相同；（后来感觉没必要，因为都是长度相等的串，但是长度不等的串就要注意了，所以还是写在这里吧）；
(2)unsigned long long 会自动取模。所以即使乘上1e5次也不会爆orz。。这是组成原理的内容了。。我也是从别的大神那里听来的；
这到题的题意就是求有多少个连续的字子串，他由m*l个小子串组成，并且m个小子串两两互不完全相同，注意区分子串与小子串的概念；
思路是对每一个小子串赋予一个hash值，对于以ai开始的子串，如果他的小子串的hash值有m个不同值那么可以知道这个子串是符合要求的，ans++；
那么一次枚举子串的起始位置可不可以呢？可以看出肯定不行，o(n^2)的复杂度；
其实对于已经找到的一个子串，我们只需要除去他的最开头的那个小子串，加上它末尾后一个小子串，不断循环下去，就可以得到一系列的子串；
因此可以把原来的串分成l个系列，每一个系列中的子串，都是可以由第一个子串减去一个小子串，加上一个新子串得到；由此降到了o(n)的复杂度；
具体细节参考代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<map> #define N 100005 #define lc rt<<1 #define rc rt<<1|1 using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e5+10; const int seed = 31; char s[maxn]; int m,l; int next[maxn]; ull h[maxn]; ull base[maxn]; map<ull, int> mp; ull string_hash(int l, int r) { return h[r] - h[l-1]*base[r-l+1];//熟练掌握字符串哈希的写法，有点类似前缀和的思想； } int main() { //freopen("in","r",stdin); base[0] = 1; for(int i = 1; i < maxn; ++i) base[i] = base[i-1]*seed;//每一位的权重； while(~scanf("%d%d",&m,&l)) { scanf("%s",s+1); int len = strlen(s+1); h[0] = 0; for(int i = 1; i <= len; ++i) h[i] = h[i-1]*seed + s[i] - 'a';//对整个字符串进行哈希； int ans = 0; for(int i = 1; i <= l&&i + m*l<= len; ++i)//注意循环条件的判断 { mp.clear(); for(int j = i; j < i + m*l ; j+=l) { ull x = string_hash(j,j+l-1); //printf("%lld ",x); mp[x]++; } //printf("\n"); if(mp.size() == m) ans++;//mp自带去重，好用啊！ //printf("%d %d\n",i,ans); for(int j = i + m*l; j + l-1 <= len; j += l)//细细体会。。。。去头添尾； { ull x = string_hash(j,j+l-1); mp[x]++; ull y = string_hash(j-m*l,j-m*l+l-1); mp[y]--; if(mp[y] == 0) mp.erase(y); if(mp.size() == m) ans++; } } printf("%d\n",ans); } }
