poj 1200 Crazy Search(hash)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接 ：http://poj.org/problem?id=1200

思路分析 ：从数据来看，该题目使用线性时间算法，可见子串的比较是不可能的；使用hash可以在常数时间内查找，可以常数时间内判重，

可以再线性时间内解决问题；问题关键在与Hash函数的选择，使得子串之间的Hash值不同；由于NC的提示，使用NC作为基数，其他字符

分配不同的数码，从1-NC，再求取Hash值，保证函数为单一映射；

代码如下 ：

#include <stdio.h>

#include <string.h>

const int N = ;

const int MAX_N = ;

int hash[MAX_N];

char A[N];

int value[];

int main( )

{

    int N, NC, hashVal, valueKey = ;

    int len, ans = , Count = ;

    memset( value, , sizeof( value ) );

    memset( A, , sizeof( A ) );

    memset( hash, , sizeof( hash ) );

    scanf( "%d %d\n", &N, &NC );

    scanf( "%s", A );

    len = strlen( A );

    for ( int i = ; i < len; ++i )

    {

        if ( value[A[i]] ==  )

            value[A[i]] = ++valueKey;

        if ( valueKey == NC )

            break;

    }

    for ( int i = ; i + N <= len; ++i )

    {

        hashVal = ;

        for ( int j = i; j < i + N; ++j )

            hashVal = hashVal * NC + value[A[j]] - ;

        if ( hash[hashVal] ==  )

        {

            hash[hashVal] = ;

            ans++;

        }

    }

    printf( "%d\n", ans );

    return ;

}