poj1200-Crazy Search(hash入门经典)

来源:互联网 时间:1970-01-01

Hash:一般是一个整数。就是说通过某种算法,可以把一个字符串"压缩" 成一个整数。
一,题意:
给出两个数n,nc,并给出一个由nc种字符组成的字符串。求这个字符串中长度为n的不同子串有多少种?
二,思路:
1.这个题不用匹配,因为不高效。
2.将长度为n的子串看作n位的nc进制数,将问题转化为共有多少种十进制数字。
3.哈希时,每一个字符都对应这0 ~ nc-1的一个数字。
三,步骤:
1.给nc个字母编号:0 ~ nc-1
hashArray[ch[i]] = k++;
2.明确每n个字母ch[i]对应一个n位的nc进制的数hashArray[ch[i]],如:abb---011;
3.将hashArray[]的nc进制数转换成一个十进制的整数sum,并且使lage[sum]=true标记一下
4.统计多少个不同的子串。

 1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 const int MaxNum = 20000000; 5 char ch[MaxNum]; 6 bool lage[MaxNum]; //用于标记是否为相同的子串 7 int hashArray[256]; //存储n个字母转换成整数之后再转换成nc进制的数 8 9 int main() {10 int n, nc;11 while (cin >> n >> nc >> ch) {12 int k = 0;13 int len = strlen(ch); //注意此处14 for (int i = 0; i < len; i++) {15 if (hashArray[ch[i]] == 0) {16 hashArray[ch[i]] = k++; //给nc个字母编号,如hashArray['a']=117 }18 }19 int ans = 0; //记录不同子串的种数20 for (int i = 0; i <= len - n; i++) {21 int sum = 0;22 for (int j = i; j < i + n; j++) {23 sum = sum * nc + hashArray[ch[j]];//将hashArray[]的nc进制数转换成一个十进制的整数sum24 }25 if (!lage[sum]) { //未出现过为false26 ans++;27 lage[sum] = true; //出现过的为true28 }29 }30 cout << ans << endl;31 }32 return 0;33 }
View Code

 

版权声明:本文为博主原创文章,未经博主允许不得转载。



相关阅读:
Top