专题——字符串

本篇将会缓慢更新,学到什么就写什么。

Trie 树

又称”字典树“,用来记录字符串,如下图。

如图中 $1 \to 4 \to 8 \to 13$ 就记录了字符串 $\texttt{cab}$。

Trie 树可以用来检索一个串或是其前缀有没有出现过。

我们用 $trie_{u,ch}$ 来记录结点 $u$ 上字符 $ch$ 所指向的下一个节点,每次插入一个子串的时候,如果这个字符先前没有出现过,就新建一个节点,将当前结点指向那个节点(实质就是动态开点)。

例题

洛谷P2580:于是他错误的点名开始了

Description

给你 $n \ (n \leq n \leq 10^4)$ 个名字串(互不相同),然后进行 $m \ (1 \leq m \leq 10^5)$ 次点名,每次你需要回答“名字不存在”、“第一次点到这个名字”、“已经点过这个名字”之一。所有字符串长度不超过 $50$。

Solution

可以说是 Trie 树的板子了。

Code
/*
    Author: Chocola4ever
    Date: 2021-04-28 17:53:34
    LastEditTime: 2021-04-28 18:15:44
    FilePath: \HydroOJd:\Programs\P2580.cpp
    Description: RP++
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=5e6+5;
char s[55];
int trie[N][26],tot=0,ed[N],n,m;//ed:1-already;0-not already;-1-none
void insert(char *s){
    int p=0,len=strlen(s);
    for (int i=0;i<len;++i){
        int ch=s[i]-'a';
        if (trie[p][ch]==0)
            trie[p][ch]=++tot;
        p=trie[p][ch];
    }
    ed[p]=0;
}
int search(char *s){
    int p=0,len=strlen(s);
    for (int i=0;i<len;++i){
        int ch=s[i]-'a';
        if (!trie[p][ch]) return -1;
        p=trie[p][ch];
    }
    if (ed[p]==0){
        ed[p]=1;
        return 0;
    }else return ed[p];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(ed,-1,sizeof ed);
    cin>>n;
    for (int i=1;i<=n;++i)
        cin>>s,insert(s);
    cin>>m;
    for (int i=1;i<=m;++i){
        cin>>s;
        int temp=search(s);
        if (temp==-1)
            puts("WRONG");
        if (temp==1)
            puts("REPEAT");
        if (temp==0)
            puts("OK");
    }
    return 0;
}

KMP

     Title: 专题——字符串
       Url: https://blog.ruakker.cn/index.php/string/
Author: Ruakker
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇