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
      
        2 #include
       
         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 }
       
      

 

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