【POJ 1200】Crazy Search（将字符映射为数字，将NC进制hash成10进制）

水深无声 2023-06-01 14:57 12阅读 0赞

### 题目链接 ###

[题目链接 http://poj.org/problem?id=1200][http_poj.org_problem_id_1200]

### 题意 ###

原字符串有NC个不同字母，统计原字符串长度为N的子字符串个数

### 解题思路 ###

1.  将字符按ASCII码映射成数字。
2.  将n个字符，即n位NC进制拼起来。
3.  将拼起来的n位NC进制转化为10进制。
4.  将10进制映射入hash表，每次映射判断是否已经存在。  
    若不存在，则ans++；否则将hash设置为存在

### 如何将子串（n位NC进制）映射为10进制 ###

a = 0

b = 1

c = 2

则

cbaa = 2 \* 3^3 + 1 \* 3^2 + 0 \* 3^1 + 0 \* 3^0

abcc = 0 \* 3^3 + 1 \* 3^2 + 2 \* 3^1 + 2 \* 3^0

### 时间复杂度 ###

本题用的是map红黑树，查找插入时间为log(NC)

时间复杂度O(mlog(NC))

m为原字符串长度（题中并未给出），NC为进制数

### 代码如下（G++） ###

#include <iostream> #include <string.h> #include "map" #include "string" using namespace std; typedef long long ll; double eps = 1e-7; // 将字符的ASCII码映射成整型 map <char, int> m; // 将字符串子串按nc进制转化为10进制存入 bool hashs[16000010]; int main() { ios::sync_with_stdio(false); int nc,n; string s; while(cin >> n >> nc >> s){ // 初始化 memset(hashs,false, sizeof(hashs)); m.clear(); // 将字符映射为整型 int cnt = 0; for(int i = 0;s[i]; ++i){ if(m.find(s[i]) == m.end()) m[s[i]] = cnt++; } int ans = 0; for(int i = 0;i <= s.length()-n;++i){ // 将字符串s[i...i+n-1]的NC进制数转化为10进制 int p = 0; for(int j =i;j < i+n;++j){ p = p*nc+m[s[j]]; } // 判断10进制是否存在，若存在则表示原字符串已经计数过一次 if(!hashs[p]){ ++ans; hashs[p] = true; } } cout << ans << endl; } return 0; }

转载于:https://www.cnblogs.com/zhangjiuding/p/11474022.html

[http_poj.org_problem_id_1200]: http://poj.org/problem?id=1200