Tag-字符串

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-04-06 15:14:55 |  0 Comments  |  字符串 Trie

poj - IMMEDIATE DECODABILITY Trie树模板

 题解

本题为Trie(字典树)的模板题。

我们先来说一下Trie的基本构造:

Trie树,又名字典树,故名思义,将字符串各个字符以类似字典的方式构造成一棵树,以便检索。

Trie树的每一个节点的深度代表着当前检索到的字符串的长度。而Trie树的每两个节点之间的边可以认为是代表着字典中的一个字符。

字典树的根节点是我们检索字符串的起始,我们每次检索字符串都是由这个根节点开始的。我们每检索一个字符,就顺延着当前这个字符所代表的边走向下一个节点。

有些节点会打一个flag标记,这代表着Trie树中一个单词的结束。

以上是Trie树的基本构造。

对于这个题目,它的要求是判断任意一个字符串不能是另外任意一个字符串的前缀。

所以我们对每个节点加一个cnt标记统计在建立Trie树过程中当前节点的访问次数。

所以题意在我们的思路中,就变为了:

在建Trie树的过程中,如果当前访问的节点打上了flag标记(一个单词的结尾)并且访问次数大于了1,则说明出现一个单词为其它单词的前缀。就输出not immediately decodable,如果建完Trie都不存在这样的单词,就输出immediately decodable。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s;
int num = 0;
const int maxn = 10005;
struct trie{
    int cnt;
    bool flag;
    int child[2];
}pool[maxn],root;
bool pp = false;
void init(){
    memset(pool,0,sizeof(pool));
    num = 0;
    root = pool[0];
    pp = false;
    return;
}
int sum = 0;
int main(){
    init();
    while(cin >> s){
        int len = s.size();
        if
 2019-04-05 22:47:29 |  0 Comments  |  字符串 KMP

POJ3461Oulipo -KMP模板题

 

 

不解释,就是KMP模板题……给出个人常用KMP模板QAQ

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s1;
string s2;
int n;
int cnt = 0;
const int maxn = 10005;
int nxt[maxn];
void KMP_pre(){
    int j = -1;
    nxt[0] = -1;
    for(int i = 1;i < s1.size();++i){
        while(j != -1 && s1[j+1] != s1[i])
            j = nxt[j];
        if(s1[j+1] == s1[i]){
            j++;
            nxt[i] = j;
        }
        else nxt[i] = -1;
    }
    return;
}
void KMP(){
    int j = -1; 
    cnt = 0;
    for(int i = 0;i < s2.size();++i){
        while(j != -1 && s1[j+1] != s2[i])
            j = nxt[j];
        if(s1[j+1] == s2[i])j++;
        if(j == s1.size()-1){
            cnt++;
            j = nxt[j];
        }
    }
    return;
}
int main(){
    cin >> n;
    while(n--){
        cin >> s1;
        cin >> s2;
        KMP_pre();
        KMP();
        cout << cnt << endl;
    }
    return 0;
}

 

Title - Artist
0:00