---

暴力枚舉，然后\(hash\)表判斷

復雜度\(O(26 * 20 * n)\)

---

具體而言

對于操作1：暴力枚舉刪除

對于操作2：暴力添加，注意添加不要重復

對于操作3：暴力替換，同樣的注意不要重復

---

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std;#define ri register int #define ull unsigned long long #define rep(io, st, ed) for(ri io = st; io <= ed; io ++) #define drep(io, ed, st) for(ri io = ed; io >= st; io --)const int yume = 19260817; const int sid = 4300050;char s[50]; int n, m, L, cnp; ull num, pre[50], wei[50]; int cap[sid], nxt[sid], val[sid]; ull fz[sid];inline int get(ull v) {int k = v & 4194303;for(int i = cap[k]; i; i = nxt[i])if(fz[i] == v) return i;return 0; }inline void ins(ull v) {int k = v & 4194303;int p = get(v);if(!p) {nxt[++ cnp] = cap[k]; fz[cnp] = v;cap[k] = cnp; val[cnp] = 1;}else val[p] ++; }inline ull v(int l, int r) {if(l > r) return 0;return pre[r] - pre[l - 1] * wei[r - l + 1]; }inline ull calc1(int p) { return v(1, p - 1) * wei[L - p] + v(p + 1, L); } inline ull calc2(int p, char c) { return v(1, p - 1) * wei[L - p + 1] + v(p + 1, L) + c * wei[L - p]; } inline ull calc3(int p, char c) { return v(1, p) * wei[L - p + 1] + v(p + 1, L) + c * wei[L - p]; }int main() {wei[0] = 1;rep(i, 1, 30) wei[i] = wei[i - 1] * yume;cin >> n >> m;rep(i, 1, n) {scanf("%s", s + 1); L = strlen(s + 1); num = 0;rep(j, 1, L) num = num * yume + s[j];ins(num);}rep(i, 1, m) {scanf("%s", s + 1); L = strlen(s + 1);rep(j, 1, L) pre[j] = pre[j - 1] * yume + s[j];if(get(pre[L])) { printf("-1\n"); continue; }int ans = 0;rep(j, 1, L) if(s[j] != s[j - 1]) ans += val[get(calc1(j))];rep(j, 1, L) rep(c, 'a', 'z') if(c != s[j])ans += val[get(calc2(j, c))];rep(j, 0, L) rep(c, 'a', 'z') if(c != s[j + 1])ans += val[get(calc3(j, c))];printf("%d\n", ans);}return 0; }

轉載于:https://www.cnblogs.com/reverymoon/p/10029306.html

總結

以上是生活随笔為你收集整理的luogu4407 [JSOI2009]电子字典 字符串hash + hash表的全部內容，希望文章能夠幫你解決所遇到的問題。

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