poj 1200 Crazy Search

Memory: 30476K

Time: 79MS

解题思路

题意：

    N是子串的长度，NC是原串中所含的不同字母的个数，求的是text中长度为N的不相同的子串有多少个。

 

思路：

   刚开始接触hash，还不懂用，参考了网上别人的思路。用nc进制的hash。先把每个不同的字母对应一个整数，在in数组里，所谓nc进制的hash就是

sum = ((sum * nc)+ in[text[i]] ) %  N。

源程序

 

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 16000000
int hash[N], in[125];
char text[N];

int main()
{
    int i, j, k,len, count, sum;
    int n, nc;

    freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &nc);
    scanf("%s", text);

    i=0;
    k = 1;
    while(text[i] != '\0')
    {
        if(in[text[i]] == 0)
            in[text[i]] = k++; //每个不同的字母对应一个整数，从1到nc

        if(k == nc+1) //找完所有不同的字母后跳出
            break;
        i++;
    }
    len = strlen(text);
    count = len-n+1; //如果所有的N长度的子串都不相同的话有count个

    for(i=0; i<len-n+1; i++)
    {
        sum = 0;
        for(j=i; j<i+n; j++)
        {
            sum = (sum * nc) + in[text[j]]; //nc进制hash
        }
        sum = sum % N;
        if(hash[sum] == 0) //如果不在设为在
            hash[sum] = 1;
        else count--; //如果在了个数减一
    }
    printf("%d\n", count);
    getch();
    return 0;
}