字符串1：字符串Hash、Trie、Manacher

📅 2026/7/18 23:44:41 👁️ 次浏览

一、字符串Hash1.时间复杂度O(Σlen)2.思路(1)把字符串转化为一个数字(2)对数字进行取模(除数为质数)(3)为保证准确性进行两次上述操作后构成数对塞入集合。3.代码如下#include bits/stdc.h #define int long long #define B1 233 #define B2 191 #define mod1 10000000007 #define mod2 10000000009 using namespace std; int N; string s; setpairint, int st; int gethash(string s, int B, int mod) { int ans 0; for (int i 0; i s.size(); i) { ans (ans * B s[i]) % mod; } return ans; } signed main() { scanf(%lld, N); while (N--) { cin s; st.insert({gethash(s, B1, mod1), gethash(s, B2, mod2)}); } printf(%lld, (int)(st.size())); }二、Trie1.时间复杂度O(Σlen)2.思路(1)每次更新时一直找到与新字符串的前缀不相同的位置然后在后面按后缀依次排开;(2)该过程中每次访问到一个节点就将以至该节点为止为前缀的串的个数加一(3)查询时找到所输入字符串前缀在Trie中的末端输出所记录的串的个数。3.代码如下#include bits/stdc.h #define int long long using namespace std; int T, n, q, idx, ans[3000010], a[3000010][62]; string s; int sep(char c) { if (c 0 c 9) return c - 0; else if (c a c z) return c - a 10; else return c - A 36; } void insert(string s) { int pos 0; for (int i 0; i (int) s.size(); i) { int c sep(s[i]); if (!a[pos][c]) a[pos][c] idx; pos a[pos][c]; ans[pos]; } } int query(string s) { int pos 0; for (int i 0; i (int) s.size(); i) { int c sep(s[i]); if (!a[pos][c]) return 0; pos a[pos][c]; } return ans[pos]; } signed main() { scanf(%lld, T); while (T--) { idx 0; scanf(%lld%lld, n, q); for (int i 1; i n; i) { cin s; insert(s); } for (int i 1; i q; i) { cin s; printf(%lld\n, query(s)); } for (int i 0; i idx; i) for (int j 0; j 62; j) a[i][j] 0; for (int i 0; i idx; i) ans[i] 0; } }三、Manacher1.时间复杂度O(n)2.思路(1)将原串中首尾和每两个字符之间随意插一个符号避免回文串长度为偶的讨论(2)维护一个maxr和相应的mid表示之前所扩展到的所有回文子串的最右边及其对应的中心点(3)对于每次遍历如果该位置在maxr左边则将其对应的左端的长度与该位置到maxr的长度取最小值如果在右边则初始化为1(4)扩展更新。3.代码如下#include bits/stdc.h #define int long long using namespace std; string s1, s; int n, maxr 0, mid 0, maxx 0, p[22000010]; signed main() { cin s1; s #; for (int i 0; i (int)s1.size(); i) { s.push_back(s1[i]); s.push_back(#); } n (int) s.size(); for (int i 0; i n; i) { if (maxr i) p[i] min(p[mid * 2 - i], maxr - i 1); else p[i] 1; while (i - p[i] 0 i p[i] n s[i - p[i]] s[i p[i]]) p[i]; if (i p[i] - 1 maxr) { maxr i p[i] - 1; mid i; } maxx max(maxx, p[i] * 2 - 1); } printf(%lld, maxx / 2); }

相关新闻