进制哈希
定义一个把字符串映射到整数的函数 f，这个函数 f 称为是 hash函数
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{h[i] = h[i - 1] * P + str[i];p[i] = p[i - 1] * P;
}// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{return h[r] - h[l - 1] * p[r - l + 1];
}
BKDRHash
ull BKDRHash(char *s)
{
ull P = 131, H = 0; //P = 31、131、1313、13131、131313
int n = strlen(s);
for (int i = 0; i < n; i++)
H = H * P + s[i] - 'a' + 1; // H = H * P + s[i] //两种方法
// 相当于：
// while(*s)
// H = H * P + ( *s++ ); return H;
}求字符串区间 [l, r] 的哈希值：
P[i] 表示 P 的 i 次方
ull get_hash(ull l, ull r)
{return H[r] - H[l - 1] * P [r - l + 1];
}
双值 Hash
typedef unsigned long long ull;
ull base = 131;
ull mod1 = 212370440130137957, mod2 = 1e9 + 7; ull get_hash1(string s)
{ int len = s.size(); ull ans = 0; for (int i = 0; i < len; i++) ans = (ans * base + (ull)s[i]) % mod1; return ans;
} ull get_hash2(string s)
{int len = s.size(); ull ans = 0; for (int i = 0; i < len; i++) ans = (ans * base + (ull)s[i]) % mod2; return ans;
} bool cmp(const string s, const string t)
{bool f1 = get_hash1(s) != get_hash1(t); bool f2 = get_hash2(s) != get_hash2(t); return f1 || f2;
}
进制 Hash 与最长回文串
P3501 [POI 2010] ANT-Antisymmetry - 洛谷 | 计算机科学教育新生态 (luogu. com. cn)
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 5e5 + 10;
char s[N], t[N];
int n, PP = 131;
long long ans;
ull P[N], f[N], g[N]; // P: 计算 PP 的 i 次方, f: s 的前缀哈希值, g: t 的前缀哈希值void bin_search(int x) // 用二分法寻找以 s[x] 为中心的回文串
{
int l = 0, r = min(x, n - x);
while (l < r)
{
int mid = (l + r + 1) >> 1;
if ((ull)(f[x] - f[x - mid] * P[mid]) == (ull)(g[x + 1] - g[x + 1 + mid] * P[mid]))
l = mid;
else
r = mid - 1;
}
ans += l; // 最长回文串的长度为 l ,它内部有 l 个回文串
}int main()
{
cin >> n;
scanf("%s", s + 1);
P[0] = 1;
for (int i = 1; i <= n; i++)
s[i] == '1' ? t[i] = '0' : t[i] = '1'; // t是反串
for (int i = 1; i <= n; i++)
P[i] = P[i - 1] * PP; // P[i]是PP的i次方
for (int i = 1; i <= n; i++)
f[i] = f[i - 1] * PP + s[i]; // 求s所有前缀的哈希值
for (int i = n; i >= 1; i--)
g[i] = g[i + 1] * PP + t[i]; // 求t所有前缀的哈希值
for (int i = 1; i <= n; i++)
bin_search(i);
cout << ans << endl;
}
进制哈希与循环节
P4391 [BOI 2009] Radio Transmission 无线传输 - 洛谷 | 计算机科学教育新生态 (luogu. com. cn)
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 1e6 + 100;
ull PP = 131;
char s[N];
ull P[N], H[N], n;
ull get_hash(ull l, ull r) // 区间[l, r]的哈希值
{
return H[r] - H[l - 1] * P[r - l + 1];
}
int main()
{
P[0] = 1;
for (int i = 1; i <= N - 1; i++)
P[i] = P[i - 1] * PP; // 预处理 PP 的 i 次方
cin >> n;
scanf("%s", s + 1); // s[0]不用
for (ull i = 1; i <= n; i++)
H[i] = H[i - 1] * PP + s[i]; // 预处理所有前缀的哈希值
for (ull i = 1; i <= n; i++)
{
ull flag = 1;
ull last = get_hash(1, i); // 暴力验证区间[l,r]是否为循环节
for (int j = 1; (j + 1) * i <= n; j++) // 逐个区间判断
{
if (get_hash(j * i + 1, (j + 1) * i) != last) // 这一区间是否与第一区间相同
{
flag = 0;
break;
}
}
if (n * i != 0) // 末位多了一小节, 单独判断
{
ull len = n % i;
if (get_hash(1, len) != get_hash(n - len + 1, n))
flag = 0;
}
if (flag)
{
cout << (int)i << endl; // 找到了答案, 输出然后退出
break;
}
}
}平方探测法
平方探测法是一种处理 哈希表 冲突的方法，其基本思想是在发生冲突时，通过计算一个增量来寻找下一个空闲位置。增量的大小是通过计算键值的平方来确定的，具体公式为：next = (hash(key) + i^2) % tableSize，其中 i 是冲突发生的次数，tableSize 是哈希表的长度。
题目描述：字符串关键字的散列映射 (25 分)【详细解析】_包含英文的字符串 散列函数-CSDN博客
void solve()
{
int n, p;
unordered_map<string, int> mp1;
cin >> n >> p;
int m[p];
string s;
memset(m, -1, sizeof(m)); for (int i = 1; i <= n; i++)
{
cin >> s;
if (mp1.count(s))
{
cout << mp1[s];
continue;
}
reverse(s.begin(), s.end());
int sum = 0;
int cnt = 0;
for (auto j : s)
{
sum += (j - 'A') * pow(32, cnt);
cnt++;
if (cnt == 3)
break;
}
reverse(s.begin(), s.end()); int key = sum % p;
//平方探测法
if (m[key] != -1)
{
int a = 1, b = key;
while (m[key] != -1)
{
key = (b + a * a) % p;
if (m[key] == -1)
break;
key = (b - a * a + p) % p;
a++;
}
}
m[key]++;
mp1[s] = key;
cout << key;
if (i != n)
cout << ' ';
}
}
KMP
普通 KMP
模板一
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++;ne[i] = j;
}// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++;if (j == m){j = ne[j];// 匹配成功后的逻辑}
}
模板二
void get_Next(string s, int ne[])
{int j = 0;ne[0] = 0;for(int i = 1; i < s.size(); i ++){while(j > 0 && s[i] != s[j]) j = ne[j-1];if(s[i] == s[j]) j ++;ne[i] = j;}
}
int kmp(string s, string t) //这个函数是从s中找到t，如果存在返回t出现的位置，如果不存在返回-1
{if(t.size() == 0) return 0;get_Next(t, ne);int j = 0;for(int i = 0; i < s.size(); i ++){while(j > 0 && s[i] != t[j]) j = ne[j-1]; if(s[i] == t[j]) j++;if(j == t.size()) return i - t.size() + 1;}return -1;
}
扩展 KMP
const int N=100010;
int ne[N], ex[N];
/*扩展KMP
* next[i]:t[]的最长公共前缀
* extend[i]:s[i...n-1]与t[]的最长公共前缀
*/
void getNext (string s, int ne[])
{int j = 0, k = 1;ne[0] = (int)s.length();while (s[j] == s[j + 1] && j + 1 < (int)s.length()) j++;ne[1] = j;for(int i = 2; i < (int)s.length(); i++){if(ne[i - k] + i < ne[k] + k)ne[i] = ne[i - k];else{j = max(ne[k] + k - i, (int)0);while(i + j < (int)s.length() && s[j] == s[j + i]) j++;ne[i] = j;k = i;}}
}void exKMP(string s, string t, int ne[], int ex[])
{int j = 0, k = 0;getNext(t);while (s[j] == t[j] && j < (int)s.length() && j < (int)t.length()) j++;ex[0] = j;for (int i = 1; i < (int)s.length(); i++){if(ne[i - k] + i < ex[k] + k)ex[i] = ne[i - k];else{j = max(ex[k] + k - i, (int)0);while(i + j < (int)s.length() && j < (int)t.length() && s[j + i] == t[j]) j++;ex[i] = j;k = i;}}
}
Manacher（马拉车算法）
应用于特定场景：查找一个长度为 n 的字符串 S 中的 最长回文子串
P3805 【模板】manacher - 洛谷 | 计算机科学教育新生态
const int N = 11000002;
int n, P[N << 1];
char a[N << 1], S[N << 1];void change()
{
n = strlen(a);
int k = 0;
S[k++] = '$';
S[k++] = '#';
for (int i = 0; i < n; i++)
{
S[k++] = a[i];
S[k++] = '#';
}
S[k++] = '&';
n = k;
}void manacher()
{
int R = 0, C;
for (int i = 1; i < n; i++)
{
if (i < R) P[i] = min(P[(C << 1) - i], P[C] + C - i);
else P[i] = 1;
while (S[i + P[i]] == S[i - P[i]]) P[i]++;
if (P[i] + i > R)
{
R = P[i] + i;
C = i;
}
}
}int main()
{
cin >> a;
change();
manacher();
int ans = 1;
for (int i = 0; i < n; i++)
ans = max(ans, P[i]);
cout << ans - 1 << endl;
}
string change(string &str)
{
string temp = "#";
for (int i = 0; str[i]; ++i)
(temp += str[i]) += "#";
return temp;
}int main()
{
string str;
cin >> str;
str = change(str);
vector<int> r((int)str.length());
int c = 0, ans = 0;
for (int i = 1; str[i]; ++i)
{
if (c + r[c] > i) r[i] = min(r[2 * c - i], c + r[c] - i);
while (i - r[i] >= 0 && str[i - r[i]] == str[i + r[i]]) ++r[i];
--r[i];
if (i + r[i] > c + r[c]) c = i; // 注意更新C的位置
ans = max(ans, r[i]);
}
cout << ans << endl; return 0;
}
回文树（回文自动机）
Problem - 5421
#define int long long
const int N = 3e5 + 8;int s[N];struct node
{
int len, fail, son[26], siz;
void init(int _len)
{
memset(son, 0, sizeof son);
fail = siz = 0;
len = _len;
}
} tree[N];int num, last[2], ans, L, R;void init()
{
last[0] = last[1] = 0;
ans = 0; num = 1;
L = 1e5 + 8, R = 1e5 + 7;
tree[0].init(0);
memset(s, -1, sizeof s);
tree[1].init(-1);
tree[0].fail = 1;
}int getfail(int p, int d)
{
if (d)
while (s[R - tree[p].len - 1] != s[R])
p = tree[p].fail;
else
while (s[L + tree[p].len + 1] != s[L])
p = tree[p].fail;
return p;
}void insert(int x, int d)
{
if (d) s[++R] = x;
else s[--L] = x;
int fa = getfail(last[d], d);
int now = tree[fa].son[x];
if (!now)
{
now = ++num;
tree[now].init(tree[fa].len + 2);
tree[now].fail = tree[getfail(tree[fa].fail, d)].son[x];
tree[now].siz = tree[tree[now].fail].siz + 1;
tree[fa].son[x] = now;
} last[d] = now;
if (R - L + 1 == tree[now].len) last[d ^ 1] = now;
ans += tree[now].siz;
}signed main()
{
int op, n;
while (scanf("%lld", &n) != EOF)
{
init();
while (n--)
{
char ch;
scanf("%lld", &op);
if (op == 1) scanf(" %c", &ch), insert(ch - 'a', 0);
if (op == 2) scanf(" %c", &ch), insert(ch - 'a', 1);
if (op == 3) printf("%lld\n", num - 1);
if (op == 4) printf("%lld\n", ans);
}
}
}
字典树（Trie、前缀树）
模板一
P2580 于是他错误的点名开始了 - 洛谷 | 计算机科学教育新生态
const int N=800000;
int n, m;
string s;struct node
{
int cnt;
int son[26];
bool repeat;
node()
{
cnt = 0;
memset(son, false, sizeof son);
repeat = false;
}
} trie[N];int num = 0;void insert(string s)
{
int v;
int u = 0;
for (int i = 0; i < s.length(); i++)
{
v = s[i] - 'a';
if (!trie[u].son[v]) trie[u].son[v] = ++num;
u = trie[u].son[v];
}
trie[u].repeat = 1;
}int find(string s)
{
int v, u = 0, len = s.length();
for (int i = 0; i < len; i++)
{
v = s[i] - 'a';
if (!trie[u].son[v]) return 3;
u = trie[u].son[v];
}
if (!trie[u].repeat) return 3;
if (!trie[u].cnt)
{
trie[u].cnt++;
return 1;
}
return 2;
}int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> s;
insert(s);
}
cin >> m;
for (int i = 1; i <= m; ++i)
{
cin >> s;
int p = find(s);
if (p == 1) puts("OK");
else if (p == 2) puts("REPEAT");
else if (p == 3) puts("WRONG");
}
}
模板二
const int N = 1000050;int trie[N][26], cnt[N], flag[N], idx;
// 0号点既是根节点，又是空节点
// trie[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// flag[]标记是否是该单词的结尾// 插入一个字符串
void insert(string s)
{int p = 0;for (int i = 0; i < s.size(); i++){int x = s[i] - 'a';if (!trie[p][x]) trie[p][x] = ++idx;p = trie[p][x];}cnt[p]++ ;flag[p] = 1;
}// 查询字符串出现的次数
int query(string s)
{int p = 0;for (int i = 0; i < s.size(); i++){int x = s[i] - 'a';if (!trie[p][x]) return 0;p = trie[p][x];}return cnt[p];
}// 前一个单词是后一个单词的前缀，则称词表为一个词链，求最长词链所包括的单词数
int bfs()
{
int res = 0;
queue<int> q;
q.push(0);
while (q.size())
{
int now = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
if (trie[now][i]) q.push(trie[now][i]);
cnt[trie[now][i]] = cnt[now];
if (flag[trie[now][i]]) cnt[trie[now][i]]++;
}
if (res < cnt[now]) res = cnt[now];
}
return res;
}