poj 1200 Crazy Search(hash)
4543 ワード
タイトルリンク:http://poj.org/problem?id=1200
構想分析:データから見ると、このテーマは線形時間アルゴリズムを使用しており、サブ列の比較は不可能であることがわかる.hashを使用すると定数時間で検索でき、定数時間で重量を判断できます.
再線形時間内に問題を解決することができる.問題の鍵はHash関数との選択であり、サブ列間のHash値が異なる.NCのヒントのため、NCを基数、その他の文字として使用します.
異なるデジタルを割り当て、1-NCからHash値を求め、保証関数は単一マッピングである.
コードは次のとおりです.
構想分析:データから見ると、このテーマは線形時間アルゴリズムを使用しており、サブ列の比較は不可能であることがわかる.hashを使用すると定数時間で検索でき、定数時間で重量を判断できます.
再線形時間内に問題を解決することができる.問題の鍵はHash関数との選択であり、サブ列間のHash値が異なる.NCのヒントのため、NCを基数、その他の文字として使用します.
異なるデジタルを割り当て、1-NCからHash値を求め、保証関数は単一マッピングである.
コードは次のとおりです.
#include <stdio.h>
#include <string.h>
const int N = 1000000;
const int MAX_N = 16000000;
int hash[MAX_N];
char A[N];
int value[128];
int main( )
{
int N, NC, hashVal, valueKey = 0;
int len, ans = 0, Count = 0;
memset( value, 0, sizeof( value ) );
memset( A, 0, sizeof( A ) );
memset( hash, 0, sizeof( hash ) );
scanf( "%d %d
", &N, &NC );
scanf( "%s", A );
len = strlen( A );
for ( int i = 0; i < len; ++i )
{
if ( value[A[i]] == 0 )
value[A[i]] = ++valueKey;
if ( valueKey == NC )
break;
}
for ( int i = 0; i + N <= len; ++i )
{
hashVal = 0;
for ( int j = i; j < i + N; ++j )
hashVal = hashVal * NC + value[A[j]] - 1;
if ( hash[hashVal] == 0 )
{
hash[hashVal] = 1;
ans++;
}
}
printf( "%d
", ans );
return 0;
}