首页 > 代码库 > poj 1200 Crazy Search
poj 1200 Crazy Search
题目链接：http://poj.org/problem?id=1200
分析：
从数据来看，该题目使用线性时间算法，可见子串的比较是不可能的；
使用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", &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\n", ans ); return 0;}
poj 1200 Crazy Search
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。