Poj 1200
题意: 给你一个 n 和 m 以及一个有 m 个不同字母组成的字符串, 问有多少个长度为 n 的不同字符子串;
题解: 以 m 为进制进行 Hash 虽然是看了解题报告才会的但必须要理解并且学会运用: https://www.cnblogs.com/gj-Acit/archive/2013/05/15/3080734.html
- #include < cstring > // 别用 set,set 的添加是红黑树实现时间复杂度是 O(logN), 在这里会超时
- #include < cstdio > #define ull unsigned long long using namespace std;
- const int N = 1e7 + 6e6 + 5;
- using namespace std;
- int p[N];
- int len;
- char str[N];
- bool hash_[N];
- int main() {
- int n,
- m;
- scanf("%d %d %s", &n, &m, str + 1);
- len = strlen(str + 1);
- int j = 0;
- for (int i = 1; i <= len; i++) {
- if (!p[str[i]]) p[str[i]] = ++j; // 以 m 为进制数, 将各个字母分别用数字表示进行 hash
- if (j == m) break;
- }
- ull Base = 1;
- ull Hash = 0;
- for (int i = 1; i <= n; i++) { // 首先将前 n 个数将 m 进制转换为 10 进制
- Hash = Hash * m + p[str[i]] - 1; // 减一是为了因为 m 进制数为 0 到 m-1
- Base *= m;
- }
- Base /= m;
- hash_[Hash] = 1;
- int ans = 1;
- for (int i = 2; i + n <= len + 1; i++) {
- Hash = (Hash - (p[str[i - 1]] - 1) * Base) * m + p[str[i + n - 1]] - 1; // 原 Hash 减去子串首字母代表的数乘以 Base 得到的是剩下字母所生成的 10 进制数那么再乘以一个 m 在加上新进的一个字母所代表的数, 得到的是新子串所代表的 10 进制数 (即其 hash 值)
- if (!hash_[Hash]) {
- hash_[Hash] = 1;
- ans++;
- }
- }
- printf("%d\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2490237.html