POJ 1200-Crazy Search【滚动哈希】

深藏阁楼爱情的钟 2023-06-11 10:21 22阅读 0赞

**描述**

许多人喜欢解决难题，其中一些难题可能会使他们疯狂。一个这样的难题可能是在给定的文本中找到隐藏的素数。该数字可以是文本中存在的给定大小的不同子字符串的数量。您很快就会发现，您确实需要计算机的帮助和良好的算法来解决这一难题。  
您的任务是编写一个程序，该程序给定子字符串的大小N，文本NC中可能出现的不同字符的数目以及文本本身，确定出现在字符串中的大小为N的不同子字符串的数目。文本。  
  
例如，考虑N = 3，NC = 4和文本“ daababac”。在本文中可以找到大小为3的不同子字符串：“ daa”; “ aab”；“ aba”；“ bab”；“ bac”。

**输入项**

输入的第一行由两个数字N和NC组成，它们之间正好隔开一个空格。这之后是进行搜索的文本。您可以假设由可能的字符集形成的最大子字符串数不超过1600万。

**输出量**

程序应仅输出一个整数，该整数与在给定文本中找到的大小为N的不同子字符串的数量相对应。

思路：算是比较简单的哈希题了，用滚动哈希的板子就行了。

#include<cstdio>
    #include<vector>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int maxn = 1e6 + 10;
    const int inf = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    const int base = 998544323;
    ull a[maxn];
    char s[maxn];
    vector<ull> v;
    
    int main()
    {
        int n, m;
        scanf("%d%d", &n, &m);
        scanf("%s", s);
        ull p = 1e9 + 9, r = 1, h = 0;
        int len = strlen(s);
        for(int i = 0; i < n && i < len; i++) // 计算出前n位
            h = h * p + s[i], r *= p;
        if(len >= n) // 该串长度大于n， 加进去
            v.push_back(h);
        for(int i = n; i < len; i++)
            h = h * p + s[i] - s[i - n] * r, v.push_back(h);// 计算其他串的hash值
        sort(v.begin(), v.end());
        int tot = unique(v.begin(), v.end()) - v.begin();
        printf("%d\n", tot);
        return 0;
    }