poj1200-Crazy Search(hash入門經典)，poj1200-crazyhash
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']=1
17 }
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進制數轉換成一個十進制的整數sum
24 }
25 if (!lage[sum]) { //未出現過為false
26 ans++;
27 lage[sum] = true; //出現過的為true
28 }
29 }
30 cout << ans << endl;
31 }
32 return 0;
33 }
View Code
版權聲明：本文為博主原創文章，未經博主允許不得轉載。
