字符串 学习笔记

junee · 2024-08-05 20:29:57 · 算法·理论

Hash

Hash 的常规表现形式为 hsh_i=hsh_{i-1} \times base + a_i \bmod p。

此时红圈表示以 i' 为中心的回文串，根据对成那么在 i 的位置也会有一个相同的回文串。

接下来再往左右扩展，看能否扩大回文串。

如果 i' 的回文串超过了左端点怎么办？

我们没法保证此时 i 右端点那部分是回文，所以最多只能到 mr，再向右匹配。

每次我们的 mr 如果被超过了，就更新一下。

我们发现 mr 向右移动最多只能移动到 n，时间复杂度为 O(n)

例题 1

给出一个只由小写英文字符 \texttt a,\texttt b,\texttt c\ldots\texttt y,\texttt z 组成的字符串 S ,求 S 中最长回文串的长度 。

做法就是上面说的。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
const int N=1e7+1e6+10;
string s;
char a[N*2]; 
int n,p[N*2];
void init(){
    int len=0;
    a[++len]='^';
    a[++len]='#';
    for(int i=1;i<=n;i++){
        a[++len]=s[i];
        a[++len]='#';
    }
    a[++len]='$';
    n=len;
}
void manacher(){
    int mr=0,mid=1;
    for(int i=1;i<=n;i++){
        if(i<mr)p[i]=min(mr-i,p[mid*2-i]);
        else p[i]=1;
        while(a[p[i]+i]==a[i-p[i]])p[i]++;
        if(i+p[i]>mr){
            mr=i+p[i];
            mid=i;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s;
    n=s.length();
    s=' '+s;
    init();
    manacher();
    int res=0;
    for(int i=1;i<=n;i++)res=max(res,p[i]);
    cout<<res-1;
    return 0;
}

例题 2

给定一个字符串 S，求出最长的双回文串。

双回文串指将其分成两部分，两部分都是回文串。

板子题，先用 manacher 求出回文长度。

要想求出双回文串，我们不妨先求出以某个点为左端点的最长回文串。接着反方向遍历，假设遍历到一个 i，那么看它最左端点往左一个的左边的最长回文串是多少，加起来更新即可。

考虑用单调队列维护，时间复杂度 O(n)。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef pair<int,int>PII;
const int N=1e5+10;
string s;
char a[N*2];
int n,p[N*2];
int l[N*2];
void init(){
    int len=0;
    a[++len]='^';
    a[++len]='#';
    for(int i=1;i<=n;i++){
        a[++len]=s[i];
        a[++len]='#';
    }
    a[++len]='$';
    n=len;
}
void manacher(){
    int mr=0,mid;
    for(int i=1;i<=n;i++){
        if(i<mr)p[i]=min(mr-i,p[mid*2-i]);
        else p[i]=1;
        while(a[i+p[i]]==a[i-p[i]])p[i]++;
        if(p[i]+i>mr){
            mr=p[i]+i;
            mid=i;
        }
    }
}
PII q[N*2];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s;
    n=s.length();
    s=' '+s;
    init();
    manacher();
    int hh=0,tt=0;
    for(int i=1;i<=n;i++){
        while(hh<tt&&q[hh].second<i)hh++;
        l[i]=i-q[hh].first;
        if(p[i]>1)q[++tt]={i,i+p[i]-1};
    }
    int ans=0;
    for(int i=n-2;i>2;i--){
        if(i-p[i]+1<=2)continue;
        ans=max(ans,p[i]-1+l[i-p[i]+1]);
    }
    cout<<ans;
    return 0;
}

Z 函数

Z 函数又称扩展 KMP，实际上跟 KMP 没有一点关系。

Z 函数用来求解某个字符串的后缀和该字符串的最长公共前缀长度。

具体的我们记 s 为原本字符串，suf_i 为以 i 开始的后缀，z_i=lcp(s,suf_i)，[l,r] 为字符串 s_{l\rightarrow r}。

首先有一个朴素的想法暴力枚举，时间复杂度为 O(n^2)。

我们发现它非常的不优美，没有用到之前的已知的信息，我们考虑用一种类似 manacher 的做法，我们记 [l,r]，为最靠右的已知的匹配串，如果我们当前匹配到 i，根据 Z 函数的定义我们可以知道 [l,r]=[1,r-l+1]，如果 i<r，则 [r,i]=[i-l+1,r-l+1]。所以我们令 z_i=\min(r-i+1,z_{i-l+1})。然后再暴力匹配，每次如果当前的匹配串超过了 r，则更新。

void get_z(){
    z[1]=n;
    for(int i=2,l=0,r=0;i<=n;i++){
        z[i]=(r>i)?min(r-i+1,z[i-l+1]):0;
        while(a[1+z[i]]==a[i+z[i]])z[i]++;
        if(i+z[i]-1>r)l=i,r=z[i]+1-1;
    }
}

例题 1

给定两个字符串 a,b，你要求出两个数组：

对于一个长度为 n 的数组 a，设其权值为 \operatorname{xor}_{i=1}^n i \times (a_i + 1)。

板子题，对于 z 数组直接跑 Z 函数，对于 p 数组发现他要求的和 Z 函数很像，直接把字符串 a 接在 b 后面再跑 Z 函数即可，注意为了防止出现问题，在两个字符串之间加个特殊字符即可。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
const int N=2e7+10;
int z[N],p[N*2];
string a,b,c,d,e;
int n,m;
void get_z(int z[],string a,int n){
    z[1]=n;
    for(int i=2,l=0,r=0;i<=n;i++){
        z[i]=(r>i)?min(r-i+1,z[i-l+1]):0;
        while(a[1+z[i]]==a[i+z[i]])z[i]++;
        if(i+z[i]-1>r)r=i+z[i]-1,l=i;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>a>>b;
    n=a.length(),m=b.length();
    b=' '+b;
    get_z(z,b,m);
    LL ans=0;
    for(int i=1;i<=m;i++)ans^=1LL*i*(z[i]+1);
    cout<<ans<<'\n';
    c=b+'@'+a;
    get_z(p,c,m+1+n);
    ans=0;
    for(int i=1;i<=n;i++)ans^=i*1LL*(p[i+m+1]+1);
    cout<<ans;
    return 0;
}

最小表示法

最小表示法对于一个字符串 s，存在一个位置 i，使得将 s_{i \rightarrow n} 和 s_{1 \rightarrow {i-1}} 拼接起来的字符串的字典序小于其他位置拼接成的字符串的字典序。

简单想法，可以直接 O(n^2) 做。

考虑优化，这里举个例子：

我们将其先扩展成两倍，记为

用两个指针记录 i,j 现在比较的位置，k 表示我们比较了 k 位。

当存在一个位置 ss_{i+k}=ss_{j+k} 时，我们将 k 往后移动。

否则当 ss_{i+k}<ss_{j+k} 时，我们可以发现一定存在一个以 i+k-1 的字符串小于以 j+k-1，所以将 j 往后移 k+1 位，如果发现 i=j 时，将 j 移动一位，最后将 k=0。

另一种情况相似。

例题 1

给定一个字符串 s，请你求出它的最小表示法。

板子题。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
const int N=3e5+10;
int n;
int s[N],ss[N*2];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        ss[i]=ss[i+n]=s[i];
    }
    int i=0,j=1,k=1;
    while(i<=n&&j<=n){
        if(ss[i+k]==ss[j+k])k++;
        else{
            if(ss[i+k]<ss[j+k])j+=k+1;
            else i+=k+1;
            if(i==j)j++;
            k=0;
        }
    }
    for(int a=min(i,j);a<=min(i,j)+n-1;a++)cout<<ss[a]<<' '; 
    return 0;
}

例题 2

给你两个数列环，判断是否同构。

把两个数列的最小表示法的字符串弄出来，看是否相同即可。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
const int N=1e6+10;
string a,b;
char s[N*2],ss[N*2];
int n,at,bt;
int find(){
    int i=1,j=2,k=0;
    while(i<=n&&j<=n&&k<=n){
        if(s[i+k]==s[j+k])k++;
        else{
            if(s[i+k]<s[j+k])j+=k+1;
            else i+=k+1;
            if(i==j)j++;
            k=0;
        }
    }
    return min(i,j);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>a>>b;
    n=a.length();
    a=' '+a;
    b=' '+b;
    for(int i=1;i<=n;i++)s[i]=s[i+n]=a[i];
    at=find();
    for(int i=1;i<=n;i++)s[i]=s[i+n]=b[i];
    bt=find();
    for(int i=1;i<=n;i++)s[i]=s[i+n]=a[i];
    for(int i=1;i<=n;i++)ss[i]=ss[i+n]=b[i];
    for(int i=1;i<=n;i++){
        if(s[at+i-1]!=ss[bt+i-1]){
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes"<<'\n';
    for(int i=1;i<=n;i++)cout<<s[at+i-1];
    return 0;
}

例题 3

隐藏口令

没必要简化题义了，真的很简单，板子。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
const int N=1e7+10;
char a[N],s[N*2];
int n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i+n]=a[i];
    int i=1,j=2,k=0;
    while(i<=n&&j<=n&&k<=n){
        if(s[i+k]==s[j+k])k++;
        else{
            if(s[i+k]<s[j+k])j+=k+1;
            else i+=k+1;
            if(i==j)j++;
            k=0;
        }
    }
    cout<<min(i,j)-1;
    return 0;
}

ACAM

ACAM 又称为 AC 自动机，与字符串匹配中的 KMP 如出一辙，在 KMP 中每次只与一个模式串匹配，在 ACAM 中，每一次都会与若干模式串一起匹配。

由于字符匹配一个一个匹配太劣了，我们选择在 trie 上一起匹配。

这里一般使用 bfs 进行匹配，假设我们正在匹配 p 节点的某个儿子，这里我们可以发现一定可以证明前面的所有信息已经都匹配完毕，可以利用之前的信息进行匹配。

具体的，我们假设匹配到了 tr_{u,i} 即 u 节点上的第 i 个儿子。

如果它存在，则将他的 fail 设置为 tr_{fail_u,i} 这里应该比较好理解，解释一下，由于 fail_u 已知，那么此时你知道匹配的部分是相同的，则两个字符串再往后加一个相同的字符，仍然是匹配的。

否则，我们将 tr_{u,i} 设置为 tr_{fail_u,i}，这里类似一个并查集的状态压缩，这样当其他节点指到这个节点时就会再往前跳。

void build(){
        memset(fail,0,sizeof fail);
        for(int i=0;i<26;i++){
            if(tr[0][i])q.push(tr[0][i]);
        }
        while(q.size()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(tr[u][i]){
                    fail[tr[u][i]]=tr[fail[u]][i];
                    q.push(tr[u][i]);
                }
                else tr[u][i]=tr[fail[u]][i];
            }
        }
    }

例题 1

给定 n 个字符串，求字符串 s 中包含有若多少种字符串。

直接在 fail 链上跳，每次加后就将当前节点设为 -1。

#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
#include<queue>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
const int N=1e6+10;
string s;
int n;
struct ACAM{
    queue<int>q;
    int cnt;
    int tr[N][26],fail[N],f[N];
    void insert(string s){
        int p=0;
        for(int i=0;s[i];i++){
            int x=s[i]-'a';
            if(!tr[p][x])tr[p][x]=++cnt;
            p=tr[p][x];
        }
        f[p]++;
    }
    void build(){
        memset(fail,0,sizeof fail);
        for(int i=0;i<26;i++){
            if(tr[0][i])q.push(tr[0][i]);
        }
        while(q.size()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(tr[u][i]){
                    fail[tr[u][i]]=tr[fail[u]][i];
                    q.push(tr[u][i]);
                }
                else tr[u][i]=tr[fail[u]][i];
            }
        }
    }
    int query(string s){
        int p=0,ans=0;
        for(int i=0,x;s[i];i++){
            x=tr[p][s[i]-'a'];
            while(x&&f[x]!=-1)ans+=f[x],f[x]=-1,x=fail[x];
            p=tr[p][s[i]-'a'];
        }
        return ans;
    }
}acam;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        acam.insert(s);
    }
    acam.build();
    cin>>s;
    cout<<acam.query(s);
    return 0;
}

例题 2

给定你 n 个字符串，输出每个字符串在所有字符串中出现的次数。

仍然是建一台 ACAM，你可以首先一个队列，这样队列的逆序就是一个拓扑序，然后逆着加回去就可以了。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
#include<queue>
#include<map>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
const int N=1e6+10;
int n;
string s;
map<int,string>mp;
struct ACAM{
    int q[N];
    int cnt,st[N];
    struct trie{
        int s[26],fail,id,sz;
    }tr[N];
    void insert(string s,int idx){
        int p=0;
        for(int i=0;s[i];i++){
            int x=s[i]-'a';
            if(!tr[p].s[x])tr[p].s[x]=++cnt;
            p=tr[p].s[x];
            tr[p].sz++;
        }
        tr[idx].id=p;
    }
    void build(){
        int hh=0,tt=-1;
        for(int i=0;i<26;i++){
            if(tr[0].s[i])q[++tt]=tr[0].s[i];
        }
        while(hh<=tt){
            int u=q[hh++];
            for(int i=0;i<26;i++){
                if(tr[u].s[i]){
                    tr[tr[u].s[i]].fail=tr[tr[u].fail].s[i];
                    q[++tt]=tr[u].s[i];
                }
                else tr[u].s[i]=tr[tr[u].fail].s[i];
            }
        }
    }
    void output(){
        for(int i=cnt-1;i>=0;i--)tr[tr[q[i]].fail].sz+=tr[q[i]].sz;
        for(int i=1;i<=n;i++)cout<<tr[tr[i].id].sz<<'\n';
    }
}acam;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        acam.insert(s,i);
    }
    acam.build();
    acam.output();
    return 0;
}

后缀数组(SA)

后缀数组一般用来求解某个字串所有后缀的字典序排序后的结果 sa，并且可以求出其相邻两个的最长公共前缀 height。

最朴素的想法可以用二分哈希做，时间复杂度为 O(n \log^2 n)。

而用后缀数组可以做到 O(n \log n)。

先理解几个数组的定义，sa_i 表示排名第 i 的是第几个后缀(或者说起始位置的下标)，rk_i 表示第 i 个后缀的排名，height_i 表示第 i 和 i-1 个后缀的最长公共前缀。

对于 sa 和 rk 数组有个重要的性质，sa_{rk_i}=rk_{sa_i}=i。

求解 sa 数组：

使用倍增来求解，倍增两部分关键字的长度，记为 k。考虑将一个后缀分成两部分，前一部分为第一关键字，后一部分为第二关键字。记 x_i 为第一关键字，y_i 为第二关键字。

首先先以第一关键字排序，用基数排序(类似桶排序，先用桶存起来，在做前缀和，再反向排序)。

接着以第二关键字排序，由于最后 k 个没有第二关键字，排名最小先分配。当某个后缀的长度也就是 sa_i \le k 时，他的长度不够无法作为第二关键字， 如果满足的话，我们就将其放入 y 数组，放入的 sa_i-k 表示第二关键字起始的位置。再进行桶排序，x_{y_i}表示 y_i 这个位置的后缀在以第一关键字的的位置,再用桶排序,记得要清空 y_i 以防误用。

对于现在的 sa_i 在下一次中他的第一关键字肯定还是最小的，然后再更新，看第一关键字和第二关键字是否相等，相等则编号相同，否则 +1，然后更新离散范围，如果离散完了就结束。

void get_sa(){
    for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
    //按第一个字符为关键字排序
    for(int i=2;i<=m;i++)c[i]+=c[i-1];
    //前缀和
    for(int i=n;i;i--)sa[c[x[i]]--]=i;
    //倒序排序保证稳定 
    for(int i=1;i<=n;i++)cout<<sa[i]<<' '; 
    cout<<'\n';
    for(int k=1;k<=n;k*=2){
        int num=0;
        //计算Y，排名从1开始，指针指向0
        //Y[i] = j -> 以第二关键字排名，排名为i的首字母下标为j（即第j个后缀）

        for(int i=n-k+1;i<=n;i++)y[++num]=i;
        //将大小小于k的先存起来
        for(int i=1;i<=n;i++){
            if(sa[i]>k)y[++num]=sa[i]-k;//前k个第一关键字不能作为某个后缀的第二关键字,sa为以第一关键字计算的排名，从小到大枚举排名，对应的下标其实是第 sa[i] - k 个后缀的第二关键字
        }
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)c[x[i]]++;
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
        //y[i] 表示以第二关键字排序，排名为i的后缀的下标
        //x[y[i]] 表示上述后缀按照第一关键字的排名
        //tong[x[y[i]]] 表示小于等于上述排名的数量,也就是该后缀的排名
        //sa记录上述排名对应的下标为 y[i]，从后往前枚举第二关键字的排名，使得第一关键字相同的后缀也可以依靠第二关键字区分
        swap(x,y);//接下来要更新X数组，且要用到旧的X数组，Y数组接下里用不到，
        //则将两者交换，目的是将旧的X存到Y中，后面所有的Y实际就是旧的X
        // 将当前的第一关键字和第二关键字当做下一轮的第一关键字，sa中存的就是按照双关键字排序的结果。
        x[sa[1]]=1,num=1;
        for(int i=2;i<=n;i++){
        //如果新排名为i的后缀和新排名为i-1的后缀的第一关键字排名相同（前一个 == ）
            //并且它们的第二关键字排名也相同（后一个 == ），那么两个后缀的新X排名相同，否则不同
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
        }
        if(num==n)break;//后缀都不同了
        m=num;
    }
}

求解 height：

void get_height(){
    for(int i=1;i<=n;i++)rk[sa[i]]=i;//rk[i] = j - > 第i个后缀的排名为j
    for(int i=1,k=0;i<=n;i++){
        if(rk[i]==1)continue;//排名为1的height不用计算
        //设h[i]表示height[rk[i]]，即位于第i个的后缀与排名在它前一个的后缀的最长公共前缀
        if(k)k--;//由于h[i]>=h[i-1]-1，所以从k-1开始枚举
        int j=sa[rk[i]-1];//排名在i前一个的后缀的下标
        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;//如果相等，则最长公共前缀+1
        height[rk[i]]=k;
    } 
}

后缀自动机(SAM)

待施工...