Poj Solution 1200

http://poj.org/problem?id=1200

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std ;

char str[20000000+10] ;
int sub, radix, ans, index[256] ;
bool hash[20000000+10] ;

// 转化为nc进制 
void Change()
{
    int i, cnt(0) ;
    for( i=0; ; ++i ){
        if( 0 == index[ str[i] ] )
            index[ str[i] ] = cnt++ ;
        if( cnt == radix )
            break ;
    }
}

void KR()
{
    __int64 i, sum(0), p, up ;
    p = (__int64)pow( (double)radix, sub-1.0 ) ;
    //printf("  pow, %dn", p ) ;
    for( i=0; i<sub; ++i ){
        sum *= radix ;
        sum += index[ str[i] ] ;
    }
    hash[sum] = true ;
    ans = 1 ;
    up = strlen( str )-sub ;
    for( i=0; i<=up; ++i ){
        if( false == hash[sum] ){
            hash[sum] = true ;
            ++ans ;
        }
        // 用KR的思想来计算，比较节省时间。 
        sum = radix*( sum- index[ str[i] ]*p ) + index[ str[i+sub] ] ;
    }
}

int main()
{
    scanf("%d%d%s", &sub, &radix, str ) ;
    Change() ;
    KR() ;
    printf("%dn", ans ) ;
    return 0 ;
}