蓝桥杯 5.字符串

KMP&字符串哈希

KMP算法

• 字符串匹配算法, 用于匹配**模式串P(短)和文本串S(长)**中出现的所有位置, 例如, S = “ababac”, P = “aba”, 那么出现的所有位置就是1和3
• 初学KMP时, 只需记住和学会使用模板即可, 对其原理不需要过度深究
• KMP算法将原本O(n^2)的字符串匹配算法优化到了O(n), 其中精髓在于next数组(仅与模式串P有关), next数组表示此时模式串下标失配时应该移动到的位置, 也表示最长的相同真前后缀的长度

// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可
char s[N], p[M];
int nex[M];
int n = strlen(s + 1), m = strlen(p + 1);
nex[0] = nex[1] = 0; // 初始化
for(int i = 2, j = 0; i <= m; i++){// 不断匹配p[i]和p[j + 1]while(j && p[i] != p[j + 1]) j = nex[j]; // 失配if(p[i] == p[j + 1]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)
}// 通过next数组进行匹配
for(int i = 1, j = 0; i <= n; i++){while(j && s[i] != p[j + 1]) j = nex[j]; // 失配if(s[i] == p[j + 1]) j++;if(j == m) // 成功匹配一次
}

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N];
char s[N], p[N];int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> p >> s;// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可int nex[N];int n = strlen(s + 1), m = strlen(p + 1);nex[0] = nex[1] = 0; // 初始化for(int i = 2, j = 0; i <= m; i++){// 不断匹配p[i]和p[j + 1]while(j && p[i] != p[j + 1]) j = nex[j]; // 失配if(p[i] == p[j + 1]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}ll ans = 0;// 通过next数组进行匹配for(int i = 1, j = 0; i <= n; i++){while(j && s[i] != p[j + 1]) j = nex[j]; // 失配if(s[i] == p[j + 1]) j++;if(j == m) ans++; // 成功匹配一次}cout << ans << "\n";return 0;
}

字符串哈希

• (基于进制的)字符串Hash本质上是用一个数字表示一段字符串, 从而降低字符串处理的复杂度
• 这个数字是一个很大的数字, 采用unsigned int 类型, 可以自然溢出, 从而简化了去模的部分
• 还需要一个进制数base, 用于规定这个数字的进制
• Hash数组h[i]表示字符串s[1~i]的Hash值, 采用类似前缀和的形式以便于求出任意一个子串的Hash值

// 字符串Hash初始化:
typedef unsigned long long ull;
const ull base = 131; // base一般为一个质数
ull h[N];
char s[N];
for(int i = 1; i <= n; i++) h[i] = h[i - 1] * base + s[i] - 'A' + 1;// 获取子串s[l]~s[r]的Hash:
ull getHash(int l, int r){return h[r] - h[l - 1] * b[r - l + 1]; // b[i]表示base的i次方(预处理)
}

例题讲解

• 还是上一道题, 1.斤斤计较的小Z

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef unsigned long long ull;
const ull base = 131; // base一般为一个质数
ull h1[N], h2[N], b[N];
char s[N], p[N];// 获取子串s[l]~s[r]的Hash:
ull getHash(ull h[], int l, int r){return h[r] - h[l - 1] * b[r - l + 1]; // b[i]表示base的i次方(预处理)
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> p >> s;int nex[N];int n = strlen(s + 1), m = strlen(p + 1);b[0] = 1;// 字符串Hash初始化:for(int i = 1; i <= n; i++) {b[i] = b[i - 1] * base;h1[i] = h1[i - 1] * base + (int)p[i];h2[i] = h2[i - 1] * base + (int)s[i];}int ans = 0;for(int i = 1; i + m - 1 <= n; i++){if(getHash(h1, 1, m) == getHash(h2, i, i + m - 1)) ans++;}cout << ans << "\n";return 0;
}

Manacher

回文串的性质

• 类似AABAA, 对于每个i具有s[i] = s[n + 1 - i]的字符串
• 回文半径: 对于一个回文中心i, 如果他的半径为r, 如果他为奇数长度的回文串的中心, 则说明[i - r + 1, i + r - 1]为一个回文串, 如果i是偶数长度的回文中心, 则回文半径没有意义(Manacher算法会解决这个问题)
• 回文的递归性质: 某个点的回文半径相比关于某个回文中心的点的回文半径一定相等或更大

Manacher算法

• ABBA没有回文半径, Manacher就是将所有的回文串转换成奇数长度的回文串, 方法是在字符串中间和头尾插入特殊字符, 转换后变成了^#A#B**#B#A$, 这个回文串是以黑色#**为回文中心, 以5为回文半径的, 它就表示原回文串中的回文长度为5-1=4
• 位置i的回文半径以p[i]表示, 意思是在转换后的字符串中[i-p[i]+1, i+p[i]-1]是回文的

int c = 0, r = 0; // 初试都从0开始
for(int i = 1; i <= 2 * n + 1; i++){p[i] = i < r ? min(r - i, p[2 * c - i]) : 1;// 如果p[i]可以更大, 就持续更新while(s[i + p[i]] == s[i - p[i]]) p[i]++;// 如果此时i可以作为一个更好的c, 就替换if(i + p[i] > r) c = i, r = i + p[i];
}

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
int p[N];
char s[N];int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> s + 1;int c = 0, r = 0; // 初试都从0开始int n = strlen(s + 1);// 添加符号, 使其成为Manacher字符串for(int i = 2 * n + 1; i >= 1; i--){s[i] = (i & 1) ? '#' : s[i >> 1];}s[0] = '^', s[2 * n + 1] = '$';for(int i = 1; i <= 2 * n + 1; i++){p[i] = i < r ? min(r - i, p[2 * c - i]) : 1;// 如果p[i]可以更大, 就持续更新while(s[i + p[i]] == s[i - p[i]]) p[i]++;// 如果此时i可以作为一个更好的c, 就替换if(i + p[i] > r) c = i, r = i + p[i];}int ans = 0;for(int i = 1; i <= 2 * n + 1; i++){ans = max(ans, p[i] - 1);}cout << ans << "\n";return 0;
}

编程138-148

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string p;
int nex[N];void getNext(string &p){// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可nex[0] = 0; // 初始化for(int i = 1, j = 0; i < p.size(); i++){// 不断匹配p[i]和p[j + 1]while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;cin >> p;int ans = 0;getNext(p);for(int i = 0; i < p.size(); i++){ans = max(ans, nex[i]);}cout << ans << "\n";return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
string p;
ll nex[N], ans;void getNext(string &p){// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可int j = 0;nex[0] = 0; // 初始化for(int i = 1; i < p.size(); i++){// 不断匹配p[i]和p[j + 1]while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}
}ll find(ll x){if(!nex[x]) return x + 1;else return nex[x] = find(nex[x] - 1);
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n >> p;getNext(p);for(int i = 0; i < p.size(); i++){if(nex[i]) ans += (i + 1) - find(i);}cout << ans << "\n";return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string p, t;
ll nex[N], ans;
vector<ll> pre(N + 2), suf(N + 1);void getNext(string &p){// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可int j = 0;nex[0] = 0; // 初始化for(int i = 1; i < p.size(); i++){// 不断匹配p[i]和p[j + 1]while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}
}// 通过next数组进行匹配
int KMP(string p, string s, vector<ll> &f){int a = -1;memset(nex, 0, sizeof(nex));getNext(s);for(int i = 0, j = 0; i < p.size(); i++){while(j && s[j] != p[i]) j = nex[j - 1]; // 失配if(s[j] == p[i]) j++;f[i] = j;if(j == s.size()) j = nex[j - 1]; // 成功匹配一次}return a;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n, m, k; cin >> n >> m >> k >> p >> t;KMP(p, t, pre);reverse(p.begin(), p.end());reverse(t.begin(), t.end());KMP(p, t, suf);reverse(suf.begin(), suf.begin() + n);map<ll, ll> mp;for(int i = 0; i < n; i++){mp[suf[i]]++;}for(int i = 0; i < n; i++){mp[suf[i]]--;if(mp[m - pre[i]]){cout << "Yes\n";return 0;}}cout << "No\n";return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
string p, t;
ll nex[N], ans;void getNext(string &p){// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可int j = 0;nex[0] = 0; // 初始化for(int i = 1; i < p.size(); i++){// 不断匹配p[i]和p[j + 1]while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> p;getNext(p);ll tmp = p.size() - nex[p.size() - 1]; // 最小周期if(tmp != p.size() && p.size() % tmp == 0){ // 必须是周期的整数倍(不是的话就不能拼接成完整的字符串, 所以为1), 且和周期不相等, 相等则为1cout << p.size() / tmp; // 总长度/最小周期 == 最多子串的数量} else {cout << 1;}return 0;
}

142诗歌双联之谜 跟上面的诗歌双联一样, 而且比上面的题还弱了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
const ll INF = 1e14 + 9;
string s, p;
// char s[N], p[N];
ll nex[N];int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n >> s >> p;s += s;s = " " + s;p = " " + p;ll m = n; n <<= 1;for(int i = 1; i <= n; i++){if(islower(s[i])){s[i] = toupper(s[i]);} else {s[i] = tolower(s[i]);}}nex[0] = 0; // 初始化for(int i = 2, j = 0; i <= m; i++){// 不断匹配p[i]和p[j + 1]while(j && p[i] != p[j + 1]) j = nex[j]; // 失配if(p[i] == p[j + 1]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}ll ans = INF;for(int i = 1, j = 0; i <= n; i++){while(j && s[i] != p[j + 1]) j = nex[j]; // 失配if(s[i] == p[j + 1]) j++;if(j == m) {// 成功匹配一次ans = min({ans, i - m, 2 * m - i});// ans = min(ans, i - m);}}if(ans == INF) cout << "No\n";else cout << "Yes\n" << ans << "\n";return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string p;
ll nex[N], f[N];void getNext(string &p){// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可nex[0] = 0; // 初始化for(int i = 1, j = 0; i < p.size(); i++){// 不断匹配p[i]和p[j + 1]while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n >> p;ll ans = 0;getNext(p);for(int i = 0; i < n; i++){f[i] = 1;}for(int i = n; i >= 0; i--){f[nex[i] - 1] += f[i];}for(int i = 0; i < n; i++){ans += f[i];}cout << ans << "\n";return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 200010;
const int base = 131; // base一般为一个质数
ull h1[N], h2[N], p[N];
int n;
char s[N];// 获取子串s[l]~s[r]的Hash:
ull getHash1(int l, int r){return h1[r] - h1[l - 1] * p[r - l + 1];
}
ull getHash2(int l, int r){l = n - l + 1, r = n - r + 1;return h2[r] - h2[l - 1] * p[r - l + 1]; // 得到反转字符串的Hash值
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> s + 1;n = strlen(s + 1) * 2 + 1;// 添加符号, 使其成为Manacher字符串for(int i = n - 1; i; i -= 2){s[i + 1] = 'z' + 1;s[i] = s[i / 2];}s[1] = 'z' + 1;p[0] = 1;for(int i = 1, j = n; i <= n; i++, j--){ // 处理Hashh1[i] = h1[i - 1] * base + s[i] - 'a' + 1;h2[i] = h2[i - 1] * base + s[j] - 'a' + 1;p[i] = p[i - 1] * base;}int ans = 0;for(int i = 1; i <= n; i++){int l = 0, r = min(i - 1, n - i);while(l < r){int mid = l + r + 1 >> 1;if(getHash1(i - mid, i - 1) != getHash2(i + mid, i + 1)) {r = mid - 1;} else {l = mid;}}int len = i - l - 1;if(getHash1(1, len) == getHash2(n, n - len + 1)){if(s[i - l] <= 'z') ans = max(ans, l + 1 + len / 2 * 2);else ans = max(ans, l + len / 2 * 2);}len = n - (i + l);if(getHash1(1, len) == getHash2(n, n - len + 1)){if(s[i - l] <= 'z') ans = max(ans, l + 1 + len / 2 * 2);else ans = max(ans, l + len / 2 * 2);}}cout << ans << "\n";return 0;
}

146-148没写

字典树基础

朴素字符串查找

• 给n个字符串s1~sn, 再给1个字符串t, 如何快速查找t是否在s中出现过
• 朴素的方法是循环遍历s1~sn, 并比较si是否和t相等即可, 但是这个时间复杂度会比较大, 可能会超时

字典树

• 字典树也叫Trie树, 是一种树形结构, 其中每个节点可以存储(当然也可以不存储)一些变量用于表示该字符串的数量, 下图中节点上的数字表示结点编号, 每条边表示一个字符
• 建立一棵这样的树

int nex[N][27]; // nex[i][0]表示从结点i出发, 边为a的下一个结点地址
int cnt[N]; // cnt[i]表示以结点i结尾的字符串数量
int idx = 2; // 内存池, 用于动态开点
// 初始时, 只有一个结点1(作为根节点)

• 编写insert函数, 用于将一个字符串s加入进去

void insert(char s[]){ // 长度为n的字符串s插入到trie中int n = strlen(s + 1);int x = 1; // 从1开始往下走for(int i = 1; i <= n; i++){// 先检查x是否存在s[i]的边if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = idx++;x = nex[x][s[i] - 'a']; // x移动到新点上}cnt[x]++;
}

• 编写一个check函数, 用于判断某个字符串在trie中的出现的次数

int check(char s[]){int n = strlen(s + 1);int x = 1;for(int i = 1; i <= n; i++) x = nex[x][s[i] - 'a'];return cnt[x];
}

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e6 + 5;int nex[N][26];
int cnt[N];
int idx = 2;void insert(char s[]){ // 长度为n的字符串s插入到trie中int x = 1; // 从1开始往下走for(int i = 1; s[i]; i++){// 先检查x是否存在s[i]的边if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = idx++;x = nex[x][s[i] - 'a']; // x移动到新点上}cnt[x]++;
}bool check(char s[]){int x = 1;for(int i = 0; s[i]; i++) x = nex[x][s[i] - 'a'];return x;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n, m; cin >> n >> m;for(int i = 1; i <= n; i++){char s[N]; cin >> s + 1;insert(s);}for(int y = 1; y <= m; y++){char t[N]; cin >> t;cout << (check(t) ? "Y" : "N") << "\n";}return 0;
}

01Trie

介绍

插入

查询

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 32 * 1e5 + 6, M = 1e5 + 9;
int a[M], prefix[M];
int son[N][2], tot = 1;void insert(int x){int o = 1;for(int i = 30; i >= 0; i--){int y = x >> i & 1;if(!son[o][y]) son[o][y] = ++tot;o = son[o][y];}
}
int query(int x){int o = 1, res = 0;for(int i = 30; i >= 0; i--){int y = x >> i & 1;if(son[o][!y]) o = son[o][!y], res |= (1 << i);else o = son[o][y];}return res;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];}for(int i = 1; i <= n; i++){prefix[i] = prefix[i - 1] ^ a[i];}insert(0);int ans = 0;for(int i = 1; i <= n; i++){ans = max(ans, query(prefix[i]));insert(prefix[i]);}cout << ans << "\n";return 0;
}

编程149-155

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3 + 5;
string s;
map<string, ll> mp;int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;for(int i = 1; i <= n; i++){cin >> s;mp[s]++;}for(auto it : mp){if(it.second >= 2){cout << 1 << "\n";return 0;}}cout << 0 << "\n";return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
string s[N];
int nex[N][27]; // nex[i][0]表示从结点i出发, 边为a的下一个结点地址
int cnt[N]; // cnt[i]表示以结点i结尾的字符串数量
int idx = 0; // 内存池, 用于动态开点
// 初始时, 只有一个结点1(作为根节点)void insert(string &s){ // 长度为n的字符串s插入到trie中int n = s.length();int x = 0; // 从1开始往下走for(int i = 0; i < n; i++){// 先检查x是否存在s[i]的边if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = ++idx;x = nex[x][s[i] - 'a']; // x移动到新点上cnt[x]++;}}int check(string &s){int n = s.length();int x = 0, dep = 0, mx = 0;for(int i = 0; i < n; i++){x = nex[x][s[i] - 'a'];dep++;if(cnt[x] >= 2){mx = max(mx, dep);}} return mx;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;for(int i = 1; i <= n; i++){cin >> s[i];insert(s[i]);}for(int i = 1; i <= n; i++){cout << check(s[i]) << "\n";}return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string s[N];
string t[N];
int nex[N][27]; // nex[i][0]表示从结点i出发, 边为a的下一个结点地址
int cnt[N]; // cnt[i]表示以结点i结尾的字符串数量
int idx = 0; // 内存池, 用于动态开点
// 初始时, 只有一个结点1(作为根节点)void insert(string &s){ // 长度为n的字符串s插入到trie中int n = s.length();int x = 0; // 从1开始往下走for(int i = 0; i < n; i++){// 先检查x是否存在s[i]的边if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = ++idx;x = nex[x][s[i] - 'a']; // x移动到新点上cnt[x]++;}}int check(string &s){int n = s.length();int x = 0, dep = 0, mx = 0;for(int i = 0; i < n; i++){if(nex[x][s[i] - 'a']){x = nex[x][s[i] - 'a']; // 能走就走} else {return 0; // 走不了则0}} return cnt[x];}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n, m; cin >> n >> m;for(int i = 1; i <= n; i++){cin >> s[i];insert(s[i]);}for(int i = 1; i <= m; i++){cin >> t[i];cout << check(t[i]) << "\n";}return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 32 * 1e5 + 6, M = 1e5 + 9;
int a[M], prefix[M];
int son[N][2], tot = 1;void insert(int x){int o = 1;for(int i = 30; i >= 0; i--){int y = x >> i & 1;if(!son[o][y]) son[o][y] = ++tot;o = son[o][y];}
}
int query(int x){int o = 1, res = 0;for(int i = 30; i >= 0; i--){int y = x >> i & 1;if(son[o][!y]) o = son[o][!y], res |= (1 << i);else o = son[o][y];}return res;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];insert(a[i]);}ll q; cin >> q;for(int i = 1; i <= q; i++){ll x; cin >> x;cout << query(x) << "\n";}return 0;
}

153-155没写