題意 ：

• 給一長度 < 1e5 的字符串s，q < 1e5次詢問，每次問一個(gè)長 < 30 的串 t 在s中出現(xiàn)的次數(shù)，且t不可重疊。
• 例 ： “abababa“中“aba“不相交的出現(xiàn)的次數(shù)為2。

思路 ：

• 字符串題，對(duì)母串中所有長度小于等于30的串做字符串哈希，對(duì)相同哈希值的串暴力統(tǒng)計(jì)答案，每個(gè)詢問直接查詢對(duì)應(yīng)哈希值的答案。
• 也可以使用Trie/AC自動(dòng)機(jī)來通過本題。

#include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <vector> #include <unordered_map> #include <unordered_set> #include <set> #include <map> #define endl '\n' #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; const double pi = acos(-1); typedef long long ll;typedef unsigned long long ull;const int N = 1e5 + 10, P = 131;ull h[N], p[N]; ull a[N]; // 記錄每個(gè)詢問串的哈希值 char str[N];ull get(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1]; }int main() {int T;scanf("%d", &T);while (T -- ){scanf("%s", str + 1);int len = strlen(str + 1);p[0] = 1;for (int i = 1; i <= len; i ++ ){p[i] = p[i - 1] * P;h[i] = h[i - 1] * P + str[i];}int n;scanf("%d", &n);map<ull, int> ma; // 詢問串哈希值在母串中出現(xiàn)的不相交的次數(shù)map<ull, int> last; // 詢問串哈希值在母串中上次出現(xiàn)的位置的末端for (int i = 1; i <= n; i ++ ){char buf[35];scanf("%s", buf + 1);int size = strlen(buf + 1);// 處理詢問串哈希值ull x = 0;for (int j = 1; j <= size; j ++ )x = x * P + buf[j];a[i] = x;ma[a[i]] = 0;last[a[i]] = 0;}// 暴力枚舉母串中長度小于等于30的串的哈希值for (int i = 1; i <= len; i ++ ){for (int j = 0; j < 30 && i + j <= len; j ++ ){ull x = get(i, i + j);// []包含了插入，count不插入，count查詢是lognif (ma.count(x) && last[x] < i){ma[x] ++ ;last[x] = i + j;}}}for (int i = 1; i <= n; i ++ )printf("%d\n", ma[a[i]]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Singing Superstar 字符串哈希-map操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。