POJ 1200 Crazy Search 查找有多少种不同的子串（hash）

Michael阿明

发布于 2021-02-20 02:39:39

56900

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

题目链接： http://poj.org/problem?id=1200 题目大意：给定子串长度，字符中不同字符数量，以及一个字符串，求不同的子串数量。

1.采用map解题

把子串插入map，map自动去重，最后输出map的size 结果是超时的。

超时代码：

/**
 * @description: http://poj.org/problem?id=1200,采用map解题
 * @author: michael ming
 * @date: 2019/5/8 16:14
 * @modified by: 
 */
#include <iostream>
#include <stdio.h>
#include <map>
#include <string>
using namespace std;
int main()
{
    size_t sublen, diffchar;
    scanf("%d%d",&sublen,&diffchar);
    map<string, int> substring;
    string str, substr;
    cin >> str;
    size_t len = str.size();
    for(size_t i = 0, j = i+sublen-1; j < len; i++,j++)
    {
        substr = str.substr(i, sublen);
        substring.insert(pair<string, int>(substr, 1));
    }
    cout << substring.size();
    return 0;
}

2.采用hash查找

先将字符串中先后出现的字符映射成1,2,3,4…比如abac（1213）
在将每个子串对应的sublen个字符哈希得到哈希值，因为题目说可能的子串组合小于1600万种，我们把得到的哈希值对1600万求模，存在数组中置为1（初始为0）。
对后面的子串的哈希值在数组中检查，如果为0，则不存在，种类+1，如果为1，说明这种子串已存在，跳过，循环遍历字符串
hash可以实现O(1)时间复杂度查找，所以时间比较短。
该题目情况下，所有子串要求的长度是一样的，用类似m进制数的哈希函数没有冲突，如果子串长度不要求一样，则以下求解方法存在冲突可能（一个很长的子串哈希完的哈希int值溢出了，即高位舍弃变成很小的数，这可能与短字符串的哈希值一样，造成冲突）。

AC代码：

/**
 * @description: 计算子串的种数
 * @author: michael ming
 * @date: 2019/5/8 17:20
 * @modified by: 
 */
#include <iostream>
#include <string>
#include <memory.h>
using namespace std;
void chartoint(string &str, int *num)   //把字符中出现过的字符转成1开始的数字
{
    int value = 1;
    int len = str.size();
    for(int i = 0; i < len; ++i)
    {
        if(num[str[i]] == 0)
            num[str[i]] = value++;
    }
}
size_t hashfunc(int i, int j, int m, int *num, string &str)    //计算子串hash值
{
    int hashValue = 0;
    for(int k = i; k <= j; ++k)
        hashValue = hashValue*m + num[str[k]];
    return hashValue;
}
int main()
{
    const unsigned int max = 16000001;
    int num[300] = {0};
    size_t *hash = new size_t[max];
    memset(hash, 0, sizeof(hash));
    int sublen, m;
    int result = 0;
    string str;
    cin >> sublen >> m >> str;
    chartoint(str, num);
    for(int i = 0; i <= str.size()-sublen; ++i)
    {
        size_t hashValue = hashfunc(i, i+sublen-1, m, num, str)%max;
        if(!hash[hashValue])
        {
            result++;
            hash[hashValue] = 1;
        }
    }
    cout << result << endl;
    delete[] hash;
    return 0;
}