字符串总结

在介绍字符串相关的算法之前，我们先了解一下string有关的函数，s.substr(pos,len):截取子串 s.find("子串") :查找子串，stoi将字符串转化为数字 s.replace(pos,len,替换内容)

那么接下来，我们介绍字符串相关的算法：

kmp:理解这个算法之前我们要先理解一个概念，Border，其实在我刚开始学的时候也是听的晕头转向的，但是其实很多时候就可以把它理解成一个统计前后缀的数组，这个算法常用来解决字符串匹配问题，原理：利用已经匹配成功的「最长相等前后缀」，匹配失败时文本串指针 i 不回溯，只移动模式串指针 j ，避免暴力算法双重循环。

#include <bits/stdc++.h>
using namespace std;
 
/**


@brief 计算KMP的next数组


next[i]含义：模式串p[0 ~ i-1]子串的最长相等前后缀长度


next[0] = -1 哨兵，用来处理j=-1的边界


@param p 模式串


@return next数组，大小 m+1，m为模式串长度


*/
vector<int> get_next(string &p)
{
int m = p.size();
vector<int> next(m + 1);
next[0] = -1; // 哨兵：0个字符，最长前后缀长度设为-1
 
int i = 0; // i:当前正在计算next[i+1]，指向模式串待比较位置
int j = -1; // j: 当前最长相等前后缀的长度
 
while (i < m)
{
// j==-1：代表没有相等前后缀，直接往后走
// p[i]==p[j]：前后缀末尾字符相等，可以延长前后缀
if (j  -1 || p[i]  p[j])
{
i++;
j++;
next[i] = j; // p[0..i1]的最长相等前后缀长度是j
}
else
{
// 不匹配，缩短前后缀，回跳到更短的前缀继续尝试
j = next[j];
}
}
return next;
}
 

/**



@brief KMP主匹配


@param s 文本串


@param p 模式串


@return vector<int> 所有匹配成功的起始下标（0开始）


*/
vector<int> kmp(string &s, string &p)
{
vector<int> res;
int n = s.size(); // 文本串长度
int m = p.size(); // 模式串长度
if(m == 0) return res;
 
vector<int> next = get_next(p);
 
int i = 0; // i：文本串指针，永远不回退！只向前走
int j = 0; // j：模式串指针
 
while (i < n)
{
// j=-1 说明模式串要从头开始；字符相等则两个指针一起前进
if (j  -1 || s[i]  p[j])
{
i++;
j++;
}
else
{
// 字符不匹配，文本i不动，模式j跳转到next[j]
j = next[j];
}
 
// j走到模式串末尾，代表一次完全匹配成功
if (j == m)
{
// im：匹配在文本串的起始位置
res.push_back(i - m);
// 关键！不能置j=0，利用next继续向后找下一个匹配，支持重叠匹配
j = next[j];
}
}
return res;
}
 
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, p;
cin >> s >> p;
auto ans = kmp(s, p);
for(int pos : ans)
{
cout << pos << " ";
}
return 0;
}

然后是字典树，把每个字符串拆解成一个树去匹配，每个字符是边，理解比较简单，这里直接给出代码

#include<bits/stdc++.h>

using namespace std;
 
const int N = 1e6 + 5; // 所有字符串总字符数上限
// son[u][c]：u号节点，字符c对应的子节点编号
int son[N][26];
int cnt[N]; // cnt[u]：以u结尾的单词数量
int idx; // 当前用到的节点编号，根是0
 
// 初始化，多组数据记得清空
void trie_init()
{
memset(son,0,sizeof son);
memset(cnt,0,sizeof cnt);
idx = 0;
}
 
// 插入字符串s
void insert(string &s)
{
int u = 0; //从根节点出发
for(char ch : s)
{
int c = ch - 'a';
if(!son[u][c])
{
son[u][c] = ++idx; //没有子节点，新建节点
}
u = son[u][c]; //往下走
}
cnt[u]++; //单词结尾计数+1
}
 
// 查询字符串s出现多少次
int query(string &s)
{
int u = 0;
for(char ch : s)
{
int c = ch - 'a';
if(!son[u][c])
{
return 0; //这条路径不存在，没有该串
}
u = son[u][c];
}
return cnt[u]; //返回结尾计数
}
 
// 查询有多少字符串以s为前缀
int query_prefix(string &s)
{
int u = 0;
for(char ch : s)
{
int c = ch - 'a';
if(!son[u][c]) return 0;
u = son[u][c];
}
// 需要额外维护一个pre_cnt数组，每个节点记录经过该节点的单词数
// insert的时候每走到一个节点pre_cnt[u]++
return pre_cnt[u];
}
 
int main()
{
trie_init();
string s1 = "abc";
insert(s1);
string s2 = "abd";
insert(s2);
 
cout << query(s1) << endl; //1
cout << query_prefix("ab")<<endl;//2
return 0;
}

然后是求最大回文子串长度的manacher算法，核心思路是通过插入特殊字符把字符串中心确定，通过对称性简化统计过程

#include <bits/stdc++.h>

using namespace std;
 
// manacher 返回最长回文子串的长度
int manacher(string &s)
{
// 1.预处理，插入#
string t;
t += '#';
for(char c : s)
{
t += c;
t += '#';
}
int n = t.size();
vector<int> p(n,0); // p[i]回文半径
int mid = 0; // 当前最大右边界的中心
int max_r = 0; // 当前回文能到达的最右位置
int ans = 0; // 记录最大p[i]，就是原串最长回文长度
 
for(int i = 0; i < n; i++)
{
// 利用镜像点，直接初始化p[i]
if(i < max_r)
{
// i关于mid的镜像点: 2*mid - i
p[i] = min(max_r - i, p[2*mid - i]);
}
else
{
p[i] = 0; //i在右边界外面，只能从0开始扩
}
 
// 中心向外暴力扩展
while(i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] -1] == t[i + p[i] +1])
{
p[i]++;
}
 
// 更新最右边界和中心
if(i + p[i] > max_r)
{
max_r = i + p[i];
mid = i;
}
ans = max(ans, p[i]);
}
return ans;
}
 
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
cout << manacher(s) << endl;
return 0;
}

然后是字符串哈希，通过把字符串映射成一个很大的数，可以O(1)查询任意子串的哈希值，快速匹配子串是否相等

#include<bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;
 
const int N = 1e6 + 5;
const ull base = 131;
 
ull h[N]; //前缀哈希
ull powb[N];//base幂次
 
void pre(string &s)
{
int n = s.size();
powb[0] = 1;
for(int i=1;i<=n;i++)
{
powb[i] = powb[i-1] * base;
h[i] = h[i-1] * base + s[i-1]; //s是0下标，h是1下标
}
}
 
//获取[l,r]子串哈希，l,r从1开始
ull get_hash(int l,int r)
{
return h[r] - h[l-1] * powb[r - l + 1];
}
 
int main()
{
ios::sync_with_stdio(false);
string s;
cin >> s;
pre(s);
//比较子串 s[1,2] 和 s[4,5]是否相等
ull a = get_hash(1,2);
ull b = get_hash(4,5);
if(a == b) cout << "equal\n";
return 0;
}