2024.12.21

wangzilong913 · 2024-12-21 16:33:22 · 个人记录

重生之我与字符串的殊死搏斗

wangzilong913: 该死的字符串，纳命来！！

string: 就凭你？吃我一招最小表示法橫劈！！

一.最小表示法

1.基本概念：

给定一个字符串，如果我们不断把它的最后一个字符放到开头，最终得到 n 个字符串，我们称这 n 个字符串是循环重构的。这些字符串中字典序最小的一个，称为字符串 S 的最小表示。

（字典序：在比较字典序中，首先比较两个字符串的第一个字符，如果不同，则第一个字符较小的字符串更小；如果相同，则继续比较下一个字符，依此类推，直到比较完所有字符。如果一个字符串是另一个字符串的前缀，则较短的字符串更小。）

2.基本原理：

首先把 S 复制一份接在它的结尾，得到字符串 SS 。显然，以 i 开始的循环同构字符串 B[i ~ i+n-1] = SS[i ~ i+n-1。

如果在 i+k 与 j+k 处发现不相等，假设 SS[i+k] > SS[j+k] ，那么我们当然可以得知 B[i] 不是 S 的最小表示（因为存在一个更小的循环同构串 B[j] ）。除此之外，我们还可以得知 B[i+1],B[i+2]......,B[i+k] 也都不是 S 的最小表示。这是因为对于 1<=p<=k ，存在一个比 B[i+p] 更小的循环同构串 B[j+p] （从 i+p 与 j+p 开始扫描，同样会在 p=k 时发现不相等，并且 SS[j+p]>SS[j+k]）。

同理，如果 SS[i+k]<SS[j+k] ，那么 B[j+1],B[j+2]......,B[j+k] 都不是 S 的最小表示，直接跳过这些位置，一定不会遗漏最小表示。

因此，我们可以做到用 O(n) 的时间复杂度求出字符串的最小表示。

3.模板：

P1368 【模板】最小表示法

注：原题是整数的最小表示，此处写的是字符串

#include <bits/stdc++.h>
using namespace std;
int n,ans;
char a[6000010];
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>a[i];
        a[i+n] = a[i];
    }
    int i = 1,j = 2,k;
    while(i <= n && j <= n){
        for(k = 0;k < n && a[i+k] == a[j+k];k++);
        if(k == n) break;
        if(a[i+k] > a[j+k]){
            i = i + k + 1;
            if(i == j) i++;
        }
        else{
            j = j + k + 1;
            if(i == j) j++;
        }
    }
    ans = min(i,j);
    for(int i = ans;i < ans+n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

string: 居然抗住了这一刀，看来是小瞧你了。

wangzilong: 代码量又小，理解也不难，你看这string就是逊啊！！

string: 哟，这么说你很勇咯。区区蝼蚁，也妄想挑战我。看我这招Trie树诛仙锁！！

二.Trie树

1.基本概念：

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。

Trie树的基本性质：

根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。

2.实现

插入：

当需要插入一个字符串 S 时，我们令一个指针 P 起初指向根节点。然后依次扫描 S 中的每一个字符 c。

若 P 的 c 字符指向一个已经存在的节点 Q ，则令 P=Q。
若 P 的 c 字符指向空，则新建一个节点 Q ，令 P 的 c 字符指针指向 Q ，然后令 P=Q。

当 S 中的字符扫描完毕时，在当前节点 P 上标记它是一个字符串的末尾。

检索：

当需要检索一个字符串 S 在Trie树中是否存在时，我们令一个指针 P 起初指向根结点，然后依次扫描 S 中的每个字符 c ：

若 P 的 c 字符指向空，则说明 S 没有被插入过Trie树，结束检索。
若 P 的 c 字符指向一个已经存在的节点 Q ，则令 P=Q。

当 S 中的字符扫描完毕时，若当前节点 P 被标记为一个字符串的末尾，则说明 S 在Trie树中存在，否则说明 S 没有被插入过Trie树。

3.模板：

P10470 前缀统计

#include <bits/stdc++.h>
using namespace std;
int n,m;
int t[1000005][26];
int cnt[1000005];
int now;
void cha(string s){
    int p=0;
    for(int i = 0;i < (int)s.size();i++){
        if(t[p][s[i]-'a'] == 0){
            t[p][s[i]-'a'] = ++ now;
        }
        p = t[p][s[i]-'a'];
    }
    cnt[p]++;
}
int zhao(string s){
    int p=0,m=0;
    for(int i = 0;i < (int)s.size();i++){
        if(t[p][s[i]-'a'] == 0){
            return m;
        }
        p = t[p][s[i]-'a'];
        m+=cnt[p];
    }
    return m;
}
int main(){
    cin>>n>>m;
    while(n--){
        string s;
        cin>>s;
        cha(s);
    }   
    while(m--){
        string s;
        cin>>s;
        cout<<zhao(s)<<endl;
    }
    return 0;
}