浅谈字符串操作

Kalium · 2021-02-12 02:10:54 · 个人记录

这波乱搞

新年发博客？

不存在，只是开个坑

所以这篇文章干屁用

是 hash， kmp，trie 树，AC 自动机的学习笔记

好吧，我基本是深夜更新

话不多说，我们就进入鬼畜奇妙的字符串世界吧

1.HASH，哈希

此算法可能是最简单的了

我们就时将每个字符串看成 base 进制的数，然后比较哈希值，但是呢，我们一个个转换后相加会很容易爆炸，所以我们需要对 mod 取余

不过这个 mod 最好取孪生素数，不然就会被毒瘤出题人卡掉

下面给出代码

const ull base = 233;
const ull mod = 1e9 + 5;

inline ull hash(char s[]) {
    int len = strlen(s);
    ull sum = 0;

    for (int i = 0; i < len; i ++)
        sum = (sum * base + (ull)(s[i])) % mod;

    return sum;
}

接下来我门来看看 P3370

其实是模板题

只要算出每一个字符串的哈希值，然后从小到大排序，比较即可

注意，对于孪生素数，这里的数据卡掉了1e9+7

代码如下

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ull unsigned long long

const int N = 1e5 + 7;
const ull base = 233;
const ull mod = 1e9 + 5;

using namespace std;

ull a[N];

char s[N];

int n, ans = 1;

inline ull hash(char s[]) {
    int len = strlen(s);
    ull sum = 0;

    for (int i = 0; i < len; i ++)
        sum = (sum * base + (ull)(s[i])) % mod;

    return sum;
}

inline bool cmp(int x, int y) {
    return x < y;
}

int main() {
    cin >>n;

    for (int i = 1; i <= n; i ++) {
        scanf("%s", s);

        a[i] = hash(s);
    }

    sort(a + 1, a + 1 + n, cmp);

    for (int i = 1; i < n; i ++) {
        if (a[i] != a[i + 1])
            ans ++;
    } 

    cout << ans << endl;

    return 0;
}

例题的话，这里先给几道，有机会再更

咋求呢？

我们可以自我匹配，当这个 b[j + 1] == b[i]，时，说明匹配上了，我们来下一位，即 j++

那么匹配不上的话，我们就将当前的 j 给换到前面去，换到第 j 位最长 前缀 和 后缀 长度，知道能够匹配上为止，即当 b[j + 1] != b[i] 时，j == nxt[j]

当然，我们每次算完肯定要记录啊，所以在每次算完后 kmp[i] == j

然后我们贴贴代码

inline void pre() {
    int j = 0;

    for (int i = 2; i <= lb; i ++) {//第一位肯定是0，无需匹配 
        while (j && b[j + 1] != b[i])//匹配不上的时候 
            j = nxt[j];//就往回搜

        if (b[j + 1] == b[i])
            j ++;//不然往前搞 

        nxt[i] = j; //记录 
    }
}

习惯性手动操作一波

B：ababd

1.j = 0, i = 2

那么b[j + 1] != b[i] 并且 j == 0

所以nxt[i] = nxt[2] = j = 0

2.j = 0, i = 3

那么b[j + 1] == b[i] == 'a'

所以j ++

即nxt[i] = nxt[3] = j = 1

3.j = 1, i = 4

那么b[j + 1] == b[i]

所以 j ++

即nxt[i] = nxt[4] = j = 2

4.j = 2, i = 5

那么 b[j + 1] != b[i] 并且 j != 0

所以j = nxt[j] = nxt[2] = 0

那么这是b[j + 1] != b[i]，但是 j == 0

所以nxt[i] = nxt[5] = j = 0

很简单易懂吧

所以我们就解决了 kmp 算法的一半了

接下来就是正式的 kmp 了（什么，现在才到kmp，滚）

如果不行，就是 b[j + 1] != a[i]，那匹配不上，我们和上面求 nxt 一样，退到前面，退回第 j 位最长 前缀 和 后缀 长度，就是 j = nxt[j]

那么当我们匹配完毕，就是 j == lb 时，匹配完毕，ans ++

同样，为了继续匹配，我们每次匹配完毕时，应该吧 j 调整，就是 j == kmp[j]

注意，不是 每次操作 完，是 每次匹配完毕

贴下代码

inline void kmp() {
    int j = 0;

    for (int i = 1; i <= la; i ++) {//这个要从第一个字母匹配 
        while (j && b[j + 1] != a[i])//不匹配
            j = nxt[j];//往回搜

        if (b[j + 1] == a[i])
            j ++;//不然往前搞 

        if (j == lb) {//匹配完毕 
            ans ++;
            j = nxt[j];//为下次匹配做好准备 
        } 
    }
} 

样例懒得模拟了，反正这个就和求 nxt 差不多

然后推荐例题，有空更新

KMP模板

关于KMP的巧妙运用 link

关于KMP的巧妙运用 link

3.Trie树

关于踹树 trie 树

好吧我们进入正题

先来一个背景：AC自动机模板（easy）

上面说了

很明显，由图可知，根节点所有的孩子的 fail 边所指向的点都是根节点

那么我们是不是可以这样：

把所有根节点的儿子的 fail 先预处理出来

然后接下来开始匹配

我们先遍历到这个 a 的一个儿子即 k

明显的，他没有一个是能够匹配的上的，于是他的 fail 边只能指向根节点

绿色的即为第三层的 fail 边，第二层的 fail 边即为蓝色的

接下来我们遍历 b 的儿子即为 a

那么明显的有一个 a，所以这个 fail 边便可以连向 a

那我们再来遍历 c 的儿子，即为 a

那么我们同样的还能找到那个 a

再来看 y

没有与之匹配的 fail 边

便只能连向根节点

所以然后接下来便可以遍历 k 的儿子就是 i

明显，i 也没有相同的字母， fail 边还是指向根节点

再来看 k 的另一个儿子 o，明显的，我们也只能指向根节点

我们从 o 的爸爸即为 a 的 fail 看，其实可以发现是没有的

所以还是连向根节点

那么这到底是什么情况呢？

偶然？

我们看看之前所有连接的

如果我们把 pos 设为当前要求的 fail 的点，那么是不是上面所有的点的 fail 边都可以看成 pos 他爹的fail 边有无这个儿子 k

若有，fail 边连向 k

若没有，连向根节点

并且，我刚刚遍历是不是按层遍历，即为 bfs

所以我们可以用队列实现

一个个儿子遍历过去，碰到的有这个儿子（真儿子），便可查询

但是如果没有呢（假儿子）

好办，把连接假儿子的边设为他父亲这个点的 fail 边所指向的与其相同字母的儿子

代码就出来了

inline void bfs() {
    queue <int> q;

    for (int i = 0; i < 26; i ++) {
        int pos = trie[1][i];//根节点的儿子（包括真假） 

        if (pos) {//真儿子 
            fail[pos] = 1;//fail数组指向根节点 
            q.push(pos);//入队 
        }
    }//把根节点的儿子设为根节点，方便查询，并把他们入队 

    while (! q.empty()) {//开始匹配 
        int u = q.front();//取出队头 
        q.pop();//弹出 

        for (int i = 0; i < 26; i ++) {//一个个儿子遍历 
            int pos = trie[u][i];//u 的为i字母的儿子（包括真假） 

            if (pos) {//如果u的这个儿子是真儿子 
                fail[pos] = trie[fail[u]][i];//就把u这个点的儿子的fail边设置为u的fail边的那个同样的儿子 

                if (! fail[pos])
                    fail[pos] = 1;

                q.push(pos);//入队 
            } else//如果是假儿子 
                trie[u][i] = trie[fail[u]][i];// 就把u的连接假儿子的边设为u这个点的fail边所指向的与其相同字母的儿子 
        }
    }
}

接下来是查询

既然是查询哪些在文本中出现且相同的位置不同即可

我们在每次查询前跳到 fail 边即可

所以查询也是极其简单的

代码

inline int find(char *ss) {
    int len = strlen(ss + 1), pos = 1, sum = 0; 

    for (int i = 1; i <= len; i ++) {
        int c = ss[i] - 'a';
        int u = trie[pos][c];

        while (u&& cnt[u] != -1) {//有这个儿子且没被搜过 
            sum += cnt[u];//加上答案 
            cnt[u] = -1;//标记 
            u = fail[u]; //跳到fail边 
        } 

        pos = trie[pos][c];//向下继续搞 
    }

    return sum; 
}

完整代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 1e6 + 7;

using namespace std;

char s[N];

int n, tot = 1;

struct AC {
    int trie[N][27];
    int cnt[N];
    int fail[N];

    inline void insert(char *ss) {
        int len = strlen(ss + 1), pos = 1;

        for (int i = 1; i <= len; i ++) {
            int c = ss[i] - 'a';

            if (! trie[pos][c])
                trie[pos][c] = ++ tot;

            pos = trie[pos][c]; 
        } 

        cnt[pos] ++;
    }//构建trie 树 

    inline void bfs() {
        queue <int> q;

        for (int i = 0; i < 26; i ++) {
            int pos = trie[1][i];//根节点的儿子（包括真假） 

            if (pos) {//真儿子 
                fail[pos] = 1;//fail数组指向根节点 
                q.push(pos);//入队 
            }
        }//把根节点的儿子设为根节点，方便查询，并把他们入队 

        while (! q.empty()) {//开始匹配 
            int u = q.front();//取出队头 
            q.pop();//弹出 

            for (int i = 0; i < 26; i ++) {//一个个儿子遍历 
                int pos = trie[u][i];//u 的为i字母的儿子（包括真假） 

                if (pos) {//如果u的这个儿子是真儿子 
                    fail[pos] = trie[fail[u]][i];//就把u这个点的儿子的fail边设置为u的fail边的那个同样的儿子 

                    if (! fail[pos])
                        fail[pos] = 1;

                    q.push(pos);//入队 
                } else//如果是假儿子 
                    trie[u][i] = trie[fail[u]][i];// 就把u的连接假儿子的边设为u这个点的fail边所指向的与其相同字母的儿子 
            }
        }
    }

    inline int find(char *ss) {
        int len = strlen(ss + 1), pos = 1, sum = 0; 

        for (int i = 1; i <= len; i ++) {
            int c = ss[i] - 'a';
            int u = trie[pos][c];

            while (u&& cnt[u] != -1) {//有这个儿子且没被搜过 
                sum += cnt[u];//加上答案 
                cnt[u] = -1;//标记 
                u = fail[u]; //跳到fail边 
            } 

            pos = trie[pos][c];//向下继续搞 
        }

        return sum; 
    }
} ac;

int main() {
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);

    cin >> n;

    for (int i = 1; i <= n; i ++) {
        scanf("%s", s + 1);
        ac.insert(s);
    }

    ac.bfs();

    scanf("%s", s + 1);

    cout << ac.find(s) << endl;

    fclose(stdin);
    fclose(stdout);

    return 0;
}

所以

我们的 AC 自动机就结束了

浅谈字符串结束了

除夕夜开始，止于 2021.3.6