題目鏈接

題目鏈接 http://poj.org/problem?id=1200

題意

原字符串有NC個不同字母，統計原字符串長度為N的子字符串個數

解題思路

將字符按ASCII碼映射成數字。

將n個字符，即n位NC進制拼起來。

將拼起來的n位NC進制轉化為10進制。

將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為進制數

Code（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; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【POJ 1200】Crazy Search（将字符映射为数字，将NC进制hash成10进制）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。