字符串合集
基本概念
有一个字符串 \(s\)，那么它的长度记作 \(|s|\)。
子串：由一个字符串 \(s\) 的一段区间 \([l,r]\) 中的字符按顺序构成的字符串称为这个字符串的子串。
前缀：由一个字符串 \(s\) 的一段区间 \([1,r]\) 中的字符按顺序构成的字符串称为这个字符串的前缀。特别地，当 \(r < |s|\) 时，这个前缀称为真前缀。
后缀：由一个字符串 \(s\) 的一段区间 \([l,|s|]\) 中的字符按顺序构成的字符串称为这个字符串的后缀。特别地，当 \(l > 1\) 时，这个前缀称为真后缀。
border：对于一个字符串 \(s\)，既是 \(s\) 的前缀又是 \(s\) 的后缀的一个字符串称为 \(s\) 的 border。
字典树（Trie 树）
普通字典树
对于一堆字符串 \(s_1,s_2,s_3,\dots,s_n\)，如果我们想快速查找一个字符串 \(t\) 在这一堆字符串中，有哪些是它的前缀，怎么做？
暴力扫显然是 \(O(n \times |t|)\) 的。
假如我们的字符串是 i，int，integer，shw，shw666，intern 和 internet，那么我们可以建一颗树：
对于每个字符串，构建方法为：
首先，\(now\) 指向根节点，然后遍历字符串：
若节点 \(now\) 没有儿子 \(s_i\)，则创建一个节点 \(s_i\)，\(cnt\) 加一并令 \(now=cnt\)（\(cnt\) 为节点数量）；
否则直接跳到该儿子。
同时，我们记录一下哪些节点是一个字符串的结尾，那么对于每个询问，我们只要爬一遍树，看看路径上有哪些节点是被标记以该节点结尾的字符串，统计一下就是答案。
例如我们查找字符串 shw114514，此时爬树时会遇到 \(10\) 号节点被标记，除此之外没有节点被标记，所以答案为 \(1\)。
题：P8306 【模板】字典树
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+10;
int t,n,q,trie[maxn][63],cnt,e[maxn];
int id(char c){
if('a'<=c&&c<='z') return c-'a';
else if('A'<=c&&c<='Z') return 26+c-'A';
else return 52+c-'0';
}
void insert(string s){
int len=s.size(),now=0;
s=" "+s;
for(int i=1;i<=len;i++){
if(!trie[now][id(s[i])]){
trie[now][id(s[i])]=++cnt;
}
now=trie[now][id(s[i])];
e[now]++;
}
}
int query(string s){
int len=s.size(),now=0;
s=" "+s;
for(int i=1;i<=len;i++){
if(trie[now][id(s[i])]){
now=trie[now][id(s[i])];
}
else{
return 0;
}
}
return e[now];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
for(int i=0;i<=cnt;i++){
for(int j=0;j<=114;j++){
trie[i][j]=0;
}
}
for(int i=0;i<=cnt;i++){
e[i]=0;
}
cnt=0;
cin>>n>>q;
for(int i=1;i<=n;i++){
string s;
cin>>s;
insert(s);
}
for(int i=1;i<=q;i++){
string s;
cin>>s;
cout<<query(s)<<endl;
}
}
return 0;
}
01Trie
P4551 最长异或路径
给定一棵 \(n\) 个点的带权树，结点下标从 \(1\) 开始到 \(n\)。寻找树中找两个结点，求最长的异或路径。
\(1\le n \le 100000;0 < u,v \le n;0 \le w < 2^{31}\)。
首先是一个很简单的处理：我们与处理出每个节点到根节点的异或值，记为 \(s_i\)，那么两个节点之间的异或路径就可以用 \(s_x \bigoplus x_y\)，因为对于重复的路径，异或两次会消掉。
那么问题就变成了：计算 \(\max\limits_{1 \le i \le n,1 \le j \le n} s_i \bigoplus s_j\)。
我们对于每个 \(s_i\)，将它的二进制表示插入 Trie 中，然后对于每个 \(s_i\)，我们树上贪心，若第 \(x\) 位为 \(1\)，那么如果这一个点有儿子 \(0\)，那么就往 \(0\) 方向走，否则只能往 \(1\)方向走（因为异或是要求不同才是 \(1\)），反之亦然，然后取最大值就是答案了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
struct edge{
int e,v;
};
int s[N],trie[N][2],n,cnt;
vector<edge> vec[N];
void dfs(int x,int fa){
for(int i=0;i<vec[x].size();i++){
int nx=vec[x][i].e;
if(nx!=fa){
s[nx]=s[x]^vec[x][i].v;
dfs(nx,x);
}
}
}
void insert(int v){
int now=0;
for(int i=(1<<30);i;i>>=1){
bool x=(v&i);
if(!trie[now][x]){
trie[now][x]=++cnt;
}
now=trie[now][x];
}
}
int getval(int v){
int ans=0,now=0;
for(int i=(1<<30);i;i>>=1){
bool x=(v&i);
if(trie[now][!x]){
ans+=i;
now=trie[now][!x];
}
else{
now=trie[now][x];
}
}
return ans;
}
int main(){
//freopen("data.txt","r",stdin);
//freopen("my.txt","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
vec[u].push_back((edge){v,w});
vec[v].push_back((edge){u,w});
}
dfs(1,-1);
for(int i=1;i<=n;i++){
insert(s[i]);
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,getval(s[i]));
}
cout<<ans;
return 0;
}
字符串匹配算法
给定一个文本串 \(s\) 和模式串 \(t\)，问 \(t\) 在 \(s\) 中第一次出现的位置。
单模式串匹配
暴力匹配
在每个位置都进行一次匹配即可。
string a,b;
cin>>a>>b;
int sa=a.size(),sb=b.size();
for(int i=0;i<sa;i++){
if(a[i]==b[0]){
int f=1;
for(int j=0;j<sb;j++){
if(a[i+j]!=b[j])f=0;
}
if(f==1){
cout<<i;
return 0;
}
}
}
KMP
想想暴力匹配为什么会慢？
因为每次失配之后我们都要从头匹配。
KMP 就很好地优化了这一点，失配时，可以不需要再次重新匹配，而是可以找到当前位置失配时模式串应该从何处开始匹配。举个例子：
s: abcacababcab
t: abcab
令 \(i\) 为文本串匹配到何处，\(j\) 为模式串匹配到何处。
此时，我们在 \(i=j=5\) 时失配了。暴力的做法是 \(i \to 2,j \to 1\) 然后继续匹配。而其实我们可以 \(j \to 1\) 继续匹配：
s:abcacababcab
t: abcab
为什么可以这么做？
因为我们扫完了模式串的前四位，发现字符串 a 是其 \(4\) 位前缀 abca 的最长 border。那么就意味着我们在 \(2,3\) 位不可能匹配上，同时在 \(4\) 位一定可以匹配其最长 border 的长度。
那么现在问题落在了怎么求解前缀的最长 border 上。（一般前 \(i\) 位的最长 border 记为 \(next_i\) 或 \(fail_i\)）。
怎么计算 abacabab 的 \(next\) 数组？
考虑递推：
首先令 \(next_1=0\)，\(i=1,j=2\)（\(i\) 是前缀最后一位，\(j\) 是后缀最后一位）。
对于位置 \(2\)，由于 \(s_i \neq s_j\)，所以 \(next_2=0\)，然后 \(j\) 加一。
对于位置 \(3\)，由于 \(s_i = s_j\)，所以 \(next_3=next_2+1=1\)，然后 \(i,j\) 加一。
对于位置 \(4\)，由于 \(s_i \neq s_j\)，所以 \(next_4=0\)，令 \(i=0\)，然后 \(j\) 加一。
同理可得 \(next_5=1,next_6=2,next_7=3\)。
对于位置 \(8\)，此时 \(i=4,j=8\)，我们发现 \(s_i \neq s_j\)。难道 \(next_8=0\) 吗？
显然不是，既然现在这个前缀不能与 \(s_j\) 组成一个公共前后缀，那么我们就考虑更短的，查表 \(next_i=1\)，即目前匹配上的 aba 的最长 border 为 a，于是这个 a 就有可能与 \(s_j\) 组成一个 border，此时检查得 \(next_8=2\)（要是还没匹配上就继续往后跳）。
因为匹配时候的 \(i\) 是不会减的，所以 KMP 匹配的时间复杂度为 \(O(|s|+|t|)\)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int nxt[maxn],lena,lenb,j;
string a,b;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>a>>b;
lena=a.size(),lenb=b.size();
a=" "+a,b=" "+b;
for(int i=2;i<=lenb;i++){
while(j>0&&b[i]!=b[j+1]){
j=nxt[j];
}
if(b[j+1]==b[i]){
j++;
}
nxt[i]=j;
}
j=0;
for(int i=1;i<=lena;i++){
while(j>0&&b[j+1]!=a[i]){
j=nxt[j];
}
if(b[j+1]==a[i]){
j++;
}
if(j==lenb){
cout<<i-lenb+1<<endl;
j=nxt[j];
}
}
for(int i=1;i<=lenb;i++){
cout<<nxt[i]<<" ";
}
return 0;
}
STL 大法
众所周知，C++ 的 string 类是有 find 函数的。
#include<bits/stdc++.h>
using namespace std;
string a,b;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>a>>b;
cout<<int(a.find(b));
return 0;
}
这里同时贴上 HNSDFZOJ1028 的代码。（非正解）
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
string s,ans="Just a legend";
int nxt[maxn];
bool f=1;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>s;
int n=s.size();
for(int i=1;i<=n-2;i++){
if(clock()>=998000){//卡时，运行超过 998ms 输出当前最优解退出
cout<<ans<<endl;
return 0;
}
string a=s.substr(0,i);
string b=s.substr(1,n-2);
string c=s.substr(n-i,i);
int check=b.find(a);
if(a==c&&check!=-1){
ans=a;
}
}
cout<<ans;
return 0;
}
多模式串匹配
有一个文本串 \(s\) 和 \(n\) 个模式串 \(t_1,t_2,t_3,\dots,t_n\)，问这些模式串中有几个在文本串中出现过。
AC 自动机
先咕，晚上再写 qwq