字符串哈希
idea
将字符串映射成一个数值（称为哈希值），因此可以在O(1)时间内做到例如判断两个串是否相等这样的事情，优化了时间复杂度
注意，哈希值不同时字符串一定不同；哈希值相同时字符串可能不同，称为冲突
发生冲突的概率是很小的 （how？待补充）
应用
- 解决字符串匹配问题
- 求最长回文子串（二分+字符串哈希）
放一道二分+哈希例题来说明字符串哈希具体做法吧：2022牛客多校第五场G题
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 5e5+10, seed = 31;
int t, n, m;
char s[N];
int prek[N], pref[N], prec[N];
ll ansk, ansf, ansc;
ull h[N], rh[N], base[N];
inline ull Hash(int l, int r) {
return h[r] - h[l - 1] * base[r - l + 1];
}
inline ull rHash(int l, int r) {
return rh[l] - rh[r + 1] * base[r - l + 1];
}
inline bool check(int x, int r) {
return Hash(x - r + 1, x) == rHash(x, x + r - 1);
}
inline bool check2(int x, int r) {
return Hash(x - r + 1, x) == rHash(x + 1, x + r);
}
void init() {
base[0] = 1;
for (int i = 1; i <= n; i++) base[i] = base[i - 1] * seed;
h[0] = 0;
for (int i = 1; i <= n; i++) {
h[i] = h[i - 1] * seed + s[i] - 'a';
}
rh[n + 1] = 0;
for (int i = n; i >= 1; i--) {
rh[i] = rh[i + 1] * seed + s[i] - 'a';
}
}
void solve() {
//ji
for (int i = 1; i <= n; i++) {
int l = 1, r = min(i, n - i + 1), mid, ans;
while (l <= r){
mid = (l + r) >> 1;
if (check(i, mid)) {
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
ansk += prek[ans + i - 1] - prek[i - 1];
ansf += pref[ans + i - 1] - pref[i - 1];
ansc += prec[ans + i - 1] - prec[i - 1];
}
//ou
for (int i = 1; i < n; i++) {
if (s[i] != s[i + 1]) continue;
int l = 1, r = min(i, n - i), mid, ans = -1;
while (l <= r){
mid = (l + r) >> 1;
if (check2(i, mid)) {
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
if(ans == -1) continue;
ansk += prek[ans + i] - prek[i];
ansf += pref[ans + i] - pref[i];
ansc += prec[ans + i] - prec[i];
}
}
int main(){
cin >> n;
scanf("%s", s + 1);
init();
for (int i = 1; i <= n; i++) {
prek[i] = prek[i-1] + (s[i] == 'k');
pref[i] = pref[i-1] + (s[i] == 'f');
prec[i] = prec[i-1] + (s[i] == 'c');
}
solve();
printf("%lld %lld %lld\n", ansk, ansf, ansc);
system("pause");
return 0;
}
字符串匹配
单串匹配
kmp算法
点击学习 转自oiwiki，讲得真的太好了
主要思想大概是，首先对模式串（t串）进行预处理，处理出 \(nex[]\) 数组，\(nex[i] = x 表示满足 s[0...x-1] 与 s[i-x+1,i] 完全相同的最大的x\)
然后对串 \(s\) 和 \(t\) 进行匹配，如果失配时不把t串又从头开始匹配，而是不断从 \(j\) 回到 \(nex[j]\) 处，直到\(t[j]\) 可以和 \(s[i]\) 匹配
时间复杂度 \(O(m + n)\)
点击查看代码
// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 1005;
char s[N], t[N];
int n, m;
int nex[N];
int ans;
void init(){
nex[0]=nex[1]=0;
int j=0;
for(int i = 2; i <= m; i++){
while(j>0&&t[i]!=t[j+1]) j=nex[j];
if(t[i]==t[j+1]) j++;
nex[i]=j;
}
}
void kmp(){
int j=0;
for(int i = 1; i <= n; i++) {
while(j>0&&s[i]!=t[j+1]) j=nex[j];
//移动可以理解为 固定s串，t串往后挪一段，使得j位置之前与s串仍然是匹配的
if(s[i]==t[j+1]) j++;
if(j==m){
// printf("%d\n",i-m+1); //求t在s中的位置
j=0; // 继续求
ans++;
}
}
}
int main() {
while(scanf("%s", s + 1) == 1) {
if(s[1] == '#') break;
scanf("%s", t + 1);
n = strlen(s + 1);
m = strlen(t + 1);
ans = 0;
init();
kmp();
printf("%d\n", ans);
}
system("pause");
return 0;
}
多串匹配
AC自动机
点击查看代码（模板）
// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 1e6 + 10;
int T, n, m;
char s[N], t[N];
int cnt, trie[N][33], fail[N], countt[N];
//ac自动机
// p1的fail指针能连到p2 当且仅当 [root('s son)...p2] 的一段序列是[root...p1]的一段前缀
void insert(char *s, int rt) {
int len = strlen(s);
for(int i = 0; i < len; i++) {
int now = s[i] - 'a';
if(!trie[rt][now]) {
trie[rt][now] = ++cnt;
}
rt = trie[rt][now];
}
countt[rt]++; //串的个数
}
void GetFail() {
fail[1] = 0;
for(int i = 0; i < 26; i++) trie[0][i] = 1;
queue<int> q;
q.push(1);
while(!q.empty()) {
int now = q.front(); q.pop();
for(int i = 0; i < 26; i++) {
if(trie[now][i]) {
fail[trie[now][i]] = trie[fail[now]][i];
q.push(trie[now][i]);
}
else {
trie[now][i] = trie[fail[now]][i]; //失配 trie[][] 回到 1（根）
}
}
}
}
void query(char *t) {
int rt = 1;
int ans = 0;
int len = strlen(t);
for(int i = 0; i < len; i++) {
int now = t[i] - 'a';
int k = trie[rt][now];
while(k > 1 && countt[k] != -1) { // k=1 失配 回到根
ans += countt[k];
countt[k] = -1;
k = fail[k];
}
rt = trie[rt][now]; // 沿着建好的trie树往下
}
printf("%d\n", ans);
}
int main(){
scanf("%d", &n);
cnt = 1;
for(int i = 1; i <= n; i++) {
scanf("%s", s);
insert(s, 1);
}
GetFail();
scanf("%s", t);
query(t);
system("pause");
return 0;
}
回文串
求回文串的数量
1.二分 + 字符串哈希
做法是枚举回文串的中心字符，由于注意到回文串的（从中心字符往两边看的字符串都是回文的）这一性质，那么可以二分以该字符为中心的回文串的最大长度
时间复杂度 \(O(nlogn)\)
2.Manacher
时间复杂度\(O(n)\)
点击查看代码（模板）
// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 3e7 + 10;
int t, n, m;
char s[N], st[N];
int p[N];
int ans;
// Manacher
// 求最长回文串长度
void init() {
n = strlen(st);
int j = 2;
s[0] = '^';
s[1] = '#';
for(int i = 0; i < n; i++) {
s[j++] = st[i];
s[j++] = '#';
}
s[j] = '&';
n = j;
}
void Manacher() {
init();
for(int i = 0, mid = 0, r = -1; i < n; i++) {
p[i] = (i >= r) ? 1 : min(r - i, p[mid * 2 - i]);
while(s[i + p[i]] == s[i - p[i]])
p[i]++;
if(i + p[i] > r) {
r = i + p[i];
mid = i;
}
}
for(int i = 0; i < n; i++) {
ans = max(ans, p[i] - 1);
}
printf("%d\n",ans);
}
int main(){
scanf("%s", st);
Manacher();
system("pause");
return 0;
}
求所有回文串
回文自动机 （PAM）
点击查看代码（模板）
// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 5e5 + 10;
int t, n, m;
char s[N];
int fail[N]; ///失配后转移的位置
int len[N];
int sz, cnt, last;
int ch[N][33];
int num[N];
// 回文自动机 PAM
void init() {
s[0] = '^'; //不会出现在字符串中的字符，表示边界
len[1] = -1; // 1:奇根 0:偶根
fail[0] = 1;
cnt = 1;
}
int main(){
scanf("%s", s + 1);
n = strlen(s + 1);
init();
for(int i = 1; i <= n; i++) {
int j;
while(s[i] != s[i - len[last] - 1]) {
last = fail[last];
}
if(!ch[last][s[i] - 'a']) {
len[++cnt] = len[last] + 2;
j = fail[last];
while(s[i] != s[i - len[j] - 1]) { // last失配后下一个转移到的位置
j = fail[j];
}
fail[cnt] = ch[j][s[i] - 'a'];
ch[last][s[i] - 'a'] = cnt;
}
last = ch[last][s[i] - 'a'];
}
puts("");
// system("pause");
return 0;
}