学习笔记——字符串算法

本文主要是介绍学习笔记——字符串算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

字符串哈希

设一个字符串 \(s\)，长度为 \(len\)，定义一个大质数 \(base\)，那么求哈希的式子为：

\[hash(s)=\sum^{len}_ {i=1} s_i \times base^{len-i} \]

\(base\) 的次方可以由 \(power\) 数组初始化得到，那么如果把哈希当做一个 \(base\) 进制的数的话，不难想出用哈希数组 \(h\) 维护前缀和的方法求一个子串的哈希值，也就是：

\[hash(s[l:r])=h_r-h_{l-1}\times base^{r-l+1} \]

kmp

解决在“文章” \(s1\) 中匹配单词 \(s2\) 的问题。

维护一个数组 \(nxt\) 表示在单词 \(s2\) 中最大真前后缀的长度，也就是对于字符串 \(s2=\text{abababaac}\) 中 \(nxt(7)=5\)，因为 \(s2[1:5]=\text{ababa},s2[3:7]=\text{ababa}\)，所以最大真前后缀就是 \(5\)，那么当我们在更新 \(nxt\) 数组时，如果失配，也就是下一位不满足条件，该如何解决？

假设当前字符串处理到 \(i\) 位，目前最大真前后缀长为 \(j\)，那么如果出现 \(s2[i] \neq s2[j+1]\) 的情况，就是失配，因为保证 \(s2[1:j]=s2[i-j+1:i]\)，所以我们可以一直跳回 \(nxt[j]\) 的位置直到可以匹配，易得这样的复杂度是 \(O(n+m)\) 的。

同理，预处理之后，当匹配 \(s1\) 时，也可以按照同样的原理，用数组 \(f\) 记录能匹配的 \(s2\) 最长前缀，当最长前缀就是 \(s2\) 时，匹配成功。

代码

P3375 【模板】KMP字符串匹配

char s1[maxn],s2[maxn];
ll len1,len2;
ll nxt[maxn],f[maxn];
inline void get_nxt(){
    nxt[1]=0;
    for(int i=2,j=0;i<=len2;i++){
        while(j&&s2[i]!=s2[j+1]){
            j=nxt[j];
        }
        if(s2[i]==s2[j+1]) j++;
        nxt[i]=j;
    }
}
inline void kmp(){
    for(int i=1,j=0;i<=len1;i++){
        while(j==len2||(j&&s1[i]!=s2[j+1])){
            j=nxt[j];
        }
        if(s1[i]==s2[j+1]) j++;
        f[i]=j;
        if(f[i]==len2){
            printf("%d\n",i-len2+1);
        }
    }
}

例题

1.P3435 OKR-Periods of Words

可以发现，如果满足题目要求的条件的话，\(a[len(Q)+1:len(a)]\) 的部分也是 \(a\) 的一个 \(border\)，那么只要 \(border\) 越小，结果就越大，所以对于每个前缀都跳 \(nxt()\) 直到为 \(0\)。

2.P4824 Censoring S

一个很精妙的操作是，不对字符串进行修改，当我们正常匹配 \(\operatorname{kmp}\) 的时候指针 \(j\) 是不断维护的，那么如果删去一个 \(T\) 后，把 \(j\) 改为删去后已经匹配了的长度就可以继续进行，那就需要一个栈维护下标，最后把没有弹出的全部输出。

int main(){
    scanf("%s",s+1);
    scanf("%s",t+1);
    ls=strlen(s+1),lt=strlen(t+1);
    get_nxt();
    for(int i=1,j=0;i<=ls;i++){
        while(j&&s[i]!=t[j+1]) j=nxt[j];
        if(s[i]==t[j+1]) j++;
        f[i]=j;
        stac[++top]=i;
        if(f[i]==lt){
            top-=lt;
            j=f[stac[top]];
        }
    }
    for(int i=1;i<=top;i++){
        //printf("%d ",stac[i]);
        printf("%c",s[stac[i]]);
    }
    return 0;
}

3.P2375 动物园

\(num(i)\) 的实际意义为在 \(s[1:i/2]\) 中，\(border\) 的个数，那么用 \(cnt(i)\) 统计，每次处理向前跳到前半区间即可。

inline void get_nxt(){
    nxt[1]=0,cnt[1]=1;
    for(int i=2,j=0;i<=len;i++){
        while(j&&s[i]!=s[j+1]) j=nxt[j];
        if(s[i]==s[j+1]) j++;
        nxt[i]=j;
        cnt[i]=cnt[j]+1;
    }
}
inline void get_ans(){
    for(int i=2,j=0;i<=len;i++){
        while(j&&s[i]!=s[j+1]) j=nxt[j];
        if(s[i]==s[j+1]) j++;
        while((j<<1)>i) j=nxt[j];
        ans=(ans*(ll)(cnt[j]+1))%mod;
    }
}

4.P3193 HNOI2008 GT考试

若保证 \(X\) 中不包含 \(A\)，就是保证 \(X\) 中对 \(A\) 的匹配是不完全的，那么我们设置 \(dp[i][j]\) 表示目前构建的长度为 \(i\) 的 \(X\) 后缀与 \(A\) 长度为 \(j\)的前缀匹配的情况数，可以得到最后的答案为：

\[ans=\sum_{i=0}^{m-1} dp[n][i] \]

考虑转移，可以发现第 \(i\) 位的结果是由 \(i-1\) 位的结果和字符串的前缀增加一位后匹配后缀方案数得来的，而这个方案数设为 \(g[i][j]\)，表示在现有的字符串后加一个字符，使得其 \(border\) 与 \(j\) 相等的方案数，转移方程为：

\[dp[i][j]=\sum_{k=0}^{m-1} dp[i-1][k]\times g[k][j] \]

然后发现已知 \(A\) 所以 \(g\) 的整体是可以初始化出来的，那么就是矩阵乘法了，然后 \(dp \times g^n\) 后的 \(\sum_{i=0}^{m-1} dp[0][i]\) 就是答案。

int n,m,p;
char s[35];
int nxt[35];
struct mat{
    int num[35][35];
    mat(){
        memset(num,0,sizeof(num));
    }
    
}dp,g;
mat operator *(mat a,mat b){
    mat ans;
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){
                ans.num[i][j]=(ans.num[i][j]+a.num[i][k]*b.num[k][j]%p)%p;
            }
        }
    }
    return ans;
}
mat q_pow(mat x,int k){
    mat ans;
    for(int i=0;i<m;i++){
        ans.num[i][i]=1;
    }
    while(k){
        if(k&1) ans=ans*x;
        x=x*x;
        k>>=1;
    }
    return ans;
}
inline void get_nxt(){
    for(int i=2,j=0;i<=m;i++){
        while(j&&s[j+1]!=s[i]){
            j=nxt[j];
        }
        if(s[j+1]==s[i]) j++;
        nxt[i]=j;
    }
}
inline void kmp(){
    for(int i=0;i<m;i++){
        for(char ch='0';ch<='9';ch++){
            int j=i;
            while(j&&s[j+1]!=ch){
                j=nxt[j];
            }
            if(s[j+1]==ch) j++;
            g.num[i][j]=(g.num[i][j]+1)%p;
        }
    }
}
int ans=0;
int main(){
    n=read(),m=read(),p=read();
    scanf("%s",s+1);
    get_nxt();
    kmp();
    dp.num[0][0]=1;
    g=q_pow(g,n);
    dp=dp*g;
    for(int i=0;i<m;i++){
        ans=(ans+dp.num[0][i])%p;
    }
    printf("%d",ans);
    return 0;
}

Trie（字典树）

把各个字符串连成一棵树，通过标记记录每一个单词，支持插入和查询操作。

结构体封装版本操作：

struct trie{
    int nxt[maxn][26],mark[maxn],tot=0;
    inline void insert(char *s){
        int len=strlen(s+1),pos=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'a';
            if(!nxt[pos][c]){
                nxt[pos][c]=++tot;
            }
            pos=nxt[pos][c];
        }
        mark[pos]=1;
    }
    inline int find(char *s){
        int len=strlen(s+1),pos=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'a';
            if(!nxt[pos][c]){
                return 0;
            }
            pos=nxt[pos][c];
        }
        return mark[pos];
    }
}t;

例题

1.Phone List

给定 \(t\) 个长度不超过 \(n\) 的数字串，问其中是否存在两个数字串 \(S\) 和 \(T\)，使得 \(S\) 是 \(T\) 的前缀，多组数据。

当我们进行 \(\operatorname{insert(s)}\) 的操作时，会判断到是否需要新拓展一个位置 \(nxt(pos,c)\) ，且我们在每个单词的词末都会用 \(mark(pos)\) 标记，那么考虑两种情况（假设 \(S\) 是 \(T\) 的前缀）：

如果 \(S\) 在 \(T\) 之前先插入字典树，那么我们在插入 \(T\) 时就会检索到 \(S\) 的词尾。
如果 \(T\) 在 \(S\) 之前先插入字典树，那么我们在插入 \(S\) 时不会开拓任何一个 \(nxt(pos,c)\)，因为所有的 \(S\) 都在已经开拓的 \(T\) 内。

综上，我们维护一个 \(checknew\) 表示是否开拓一个新空间，维护一个 \(checkend\) 表示是否检索到一个词尾，那么当没有开拓新空间或是检索到了词尾时，就找到了符合要求的一对字符串。

注意初始化

struct trie{
    int nxt[maxn][26],mark[maxn],tot=0;
    void init(){
        tot=0;
        memset(nxt,0,sizeof(nxt));
        memset(mark,0,sizeof(mark));
    }
    inline bool insert(char *s){
        bool checkend=0,checknew=0;
        int len=strlen(s+1),pos=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'0';
            if(!nxt[pos][c]){
                nxt[pos][c]=++tot;
                checknew=1;
            }
            pos=nxt[pos][c];     
            if(mark[pos]) checkend=1;  
        }
        mark[pos]=1;
        return !checknew||checkend;
    }
}t;

2.The XOR-largest pair

可以考虑把每个数转换成 \(32\) 位的二进制字符串\(S\)，并且把 \(S\) 的每一位都取反得到另一个字符串 \(xorS\)，每次插入新的一个 \(S\) 前都在字典树中匹配 \(xorS\) 如果匹配不到则向另一方向匹配，每次匹配成功记录结果，最后维护最大值。

struct trie{
    int nxt[maxn][2],tot=0;
    inline void insert(char *s){
        int len=strlen(s+1),pos=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'0';
            if(!nxt[pos][c]){
               nxt[pos][c]=++tot;
            } 
            pos=nxt[pos][c];
        }
    }
    inline int find(char *s){
        int len=strlen(s+1),pos=0,ans=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'0';
            if(nxt[pos][c]){
                pos=nxt[pos][c];
                ans=ans+(1<<(32-i));
            }
            else pos=nxt[pos][c^1];
        }
        return ans;
    }
}t;
int n,ansx=minxn;
char s[40],xors[40];
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int num=read();
        for(int j=31;j>=0;j--){
            if(num/(1<<j)) s[32-j]='1',xors[32-j]='0';
            else s[32-j]='0',xors[32-j]='1';
            num%=(1<<j);
        }
        if(i>1) ansx=max(ansx,t.find(xors));
        t.insert(s);
    }
    printf("%d\n",ansx);
    return 0;
}

3.The XOR-longest path

用一遍 \(\operatorname{dfs}\) 遍历出每个节点到根节点路径的异或和，再按照上道题一样求最大的一对值。

4.Nikitosh 和异或

给定一个含 \(N\) 个元素的数组 \(A\)，下标从 \(1\) 开始。请找出下面式子的最大值：

\[(A[l_1] \oplus A[l_1+1] \oplus\dots \oplus A[r_1])+(A[l_2] \oplus A[l_2+1] \oplus\dots \oplus A[r_2]) \]

其中 \(1\leq l_1\leq r_1\le l2\leq r2\leq N\)，\(x\oplus y\) 表示 \(x\) 和 \(y\) 的按位异或。

我们用数组 \(l(i)\) 表示区间 \([1,i]\) 中的最大异或值，\(r(i)\) 表示区间 \([i,N]\) 中的最大异或值，那么显然有：

\[ans=\max_{i=1}^{N} \{l(i)+r(i+1)\} \]

那么只需要求得数组 \(l\) 和 \(r\) 就可以了，可以发现异或值同样拥有前缀和的性质，于是每次把 \([1,i]\) 或是 \([i,N]\) 前缀和放到字典树里跑就能得到以 \(i\) 为首元素或是尾元素的最大值，再和 \(l(i-1)\) 或是 \(r(i+1)\) 进行比较，就达到了目的。

struct trie{
    int nxt[maxn][2],tot=0;
    inline void init(){
        memset(nxt,0,sizeof(nxt));
        tot=0;
    }
    inline void insert(char *s){
        int len=strlen(s+1),pos=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'0';
            if(!nxt[pos][c]){
                nxt[pos][c]=++tot;
            }
            pos=nxt[pos][c];
        }
    }
    inline int find(char *s){
        int ans=0,len=strlen(s+1),pos=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'0';
            if(nxt[pos][c]){
                pos=nxt[pos][c];
                ans=ans+(1<<(32-i));
            }
            else pos=nxt[pos][c^1];
        }
        return ans;
    }
}t;
int n;
int a[maxn],l[maxn],r[maxn];
char s[40],xors[40];
int ansx=minxn,num=0;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<=n;i++){
        num=num^a[i];
        int tmp=num;
        for(int j=31;j>=0;j--){
            if(tmp/(1<<j)) s[32-j]='1',xors[32-j]='0';
            else s[32-j]='0',xors[32-j]='1';
            tmp%=(1<<j);
        }
        t.insert(s);
        l[i]=max(l[i-1],t.find(xors));
    }
    num=0;
    for(int i=n;i>=1;i--){
        num=num^a[i];
        int tmp=num;
        for(int j=31;j>=0;j--){
            if(tmp/(1<<j)) s[32-j]='1',xors[32-j]='0';
            else s[32-j]='0',xors[32-j]='1';
            tmp%=(1<<j);
        }
        t.insert(s);
        r[i]=max(r[i+1],t.find(xors));
    }
    for(int i=1;i<=n;i++){
        ansx=max(ansx,l[i]+r[i+1]);
    }
    printf("%d\n",ansx);
    return 0;
}

AC自动机（字典图）

原理

类似于在字典树上加上 \(\operatorname{kmp}\) 的操作，这里的指针称之为失配指针 \(fail\)，和 \(\operatorname{kmp}\) 不同的是，该指针是建在字典树上，且存在于不同模式串之间。、

fail指针

首先每个 fail[u] 的最坏情况是与根节点相连，最好情况是与父节点的失配指针判断时候匹配，如果不匹配继续向上跳父亲，直到根节点。

P3808 AC自动机（简单版）

queue<int> q;
struct AC_Automaton{
    int nxt[maxn][26],mark[maxn],fail[maxn],tot=0;
    inline void insert(char *s){
        int len=strlen(s+1),pos=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'a';
            if(!nxt[pos][c]){
                nxt[pos][c]=++tot;
            }
            pos=nxt[pos][c];
        }
        mark[pos]++;
    }
    inline void build(){
        for(int i=0;i<26;i++){
            if(nxt[0][i]){
                fail[nxt[0][i]]=0;
                q.push(nxt[0][i]);
            }
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(nxt[u][i]){
                    fail[nxt[u][i]]=nxt[fail[u]][i];
                    q.push(nxt[u][i]);
                }
                else{
                    nxt[u][i]=nxt[fail[u]][i];
                }
            }
        }
    }
    inline int query(char *s){
        int len=strlen(s+1),pos=0,ans=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'a';
            pos=nxt[pos][c];
            for(int j=pos;j&&~mark[j];j=fail[j]){
                ans+=mark[j];
                mark[j]=-1;
            }
        }
        return ans;
    }
}ac;
int n;
char s[maxm];
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        ac.insert(s);
    }
    ac.build();
    scanf("%s",s+1);
    printf("%d\n",ac.query(s));
    return 0;
}

P3796 AC自动机（加强版）

记录一下输入的字符串，然后把查询和插入操作改一下。

struct AC_Automaton{
    int nxt[maxn][26],mark[maxn],fail[maxn],tot=0;
    int ans[maxn];
    inline void clear(){
        memset(nxt,0,sizeof(nxt));
        memset(mark,0,sizeof(mark));
        memset(fail,0,sizeof(fail));
        memset(ans,0,sizeof(ans));
        tot=0;
    }
    inline void insert(char *s,int ord){
        int len=strlen(s+1),pos=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'a';
            if(!nxt[pos][c]){
                nxt[pos][c]=++tot;
            }
            pos=nxt[pos][c];
        }
        mark[pos]=ord;
    }
    inline void build(){
        for(int i=0;i<26;i++){
            if(nxt[0][i]){
                fail[nxt[0][i]]=0;
                q.push(nxt[0][i]);
            }
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(nxt[u][i]){
                    fail[nxt[u][i]]=nxt[fail[u]][i];
                    q.push(nxt[u][i]);
                }
                else{
                    nxt[u][i]=nxt[fail[u]][i];
                }
            }
        }
    }
    inline void query(char *s){
        int len=strlen(s+1),pos=0;
        for(int i=1;i<=len;i++){
            int c=s[i]-'a';
            pos=nxt[pos][c];
            for(int j=pos;j;j=fail[j]){
                ans[mark[j]]++;
            }
        }
    }
}ac;

这篇关于学习笔记——字符串算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

学习笔记——字符串算法

字符串哈希

kmp

例题

1.P3435 OKR-Periods of Words

2.P4824 Censoring S

3.P2375 动物园

4.P3193 HNOI2008 GT考试

Trie（字典树）

例题

1.Phone List

2.The XOR-largest pair

3.The XOR-longest path

4.Nikitosh 和异或

AC自动机（字典图）

原理

fail指针

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯