Trie树习题--三连_trie树上dp好题

一连：POJ  1056   http://poj.org/problem?id=1056

题意：问是否有一个串S，S是另一个字符串的前缀

思路：直接Trie建立，再从头遍历一遍，要注意的是，自己是自己的前缀，统计前缀个数时要注意一下

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
 
const int maxn = 1e4;
int trie[maxn][2];
int tot = 0;
int sum[maxn];
string str;
string s[105];
 
int idx(char s){return s -'0';}
void Insert(string s)
{
    int u = 0, len = s.length();
    for(int i = 0; i < len; i++){
        int c = idx(s[i]);
        if(!trie[u][c]) trie[u][c] = ++tot;
        sum[trie[u][c]]++;
        u = trie[u][c];
    }
}
 
int findout(string s)
{
    int u = 0, len = s.length();
    for(int i = 0; i < len; ++i){
        int c = idx(s[i]);
        if(!trie[u][c]) return 0;
        u = trie[u][c];
    }
    return sum[u];
}
 
int main()
{
    int cas = 1;
    while(cin >> str){
        for(int i = 0; i < maxn; i++){
            for(int j = 0; j < 2; j++)
                trie[i][j] = 0;
        }
        memset(sum, 0, sizeof(sum));
        int flag = 1;
        Insert(str);
        int cnt = 0;
        cin >> s[cnt];
        while(s[cnt][0] != '9'){
            Insert(s[cnt]);
            cnt++;
            cin >> s[cnt];
        }
        if(findout(str) > 1)    flag = 0;
        for(int i = 0; i < cnt; i++){
            if(findout(s[i]) > 1){
                flag = 0;
                break;
            }
        }
        if(flag == 0)   printf("Set %d is not immediately decodable\n",cas++);
        else if(flag == 1)  printf("Set %d is immediately decodable\n",cas++);
    }
    return 0;
}

二连：POJ 2001 http://poj.org/problem?id=2001

题意：给你一堆字符串，让你给出每个字符串的最短标识前缀(即这个前缀只存于这一个字符串中）

思路：建立Trie树时，用一个sum数组记录结点存储信息，在find字符串过程中，跑到只记录了一次的点结束（因为这个点只记录了一次，那么这个点一定是该点所在字符串与其它字符串不一样的地方）

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
 
const int maxn = 2e4;
int trie[maxn][26];
int idx(char c){return c - 'a';}
int tot = 0;
int sum[maxn];
 
string s[1005];
 
void insert(string s)
{
    int u = 0, len = s.length();
    for(int i = 0; i < len; i++){
        int c = idx(s[i]);
        if(!trie[u][c]) trie[u][c] = ++tot;
        u = trie[u][c];
        sum[u]++;
    }
}
 
void findout(string s)
{
    int u = 0, len = s.length();
    for(int i = 0; i < len; i++){
        int c = idx(s[i]);
        if(sum[u] == 1) return;
        printf("%c", s[i]);
        u = trie[u][c];
    }
}
 
int main()
{
    int cnt = 0;
    while(cin>>s[cnt]){
        insert(s[cnt]);
        cnt++;
    }
    for(int i = 0; i < cnt; i++){
        cout << s[i] << " " ;
        findout(s[i]);
        cout << '\n';
    }
    return 0;
}

三连：POJ 2503  http://poj.org/problem?id=2503

题意：给你两堆字符串，一一对应， 类似于明文/密文转换问题

思路：（直接map就可以）在建立Trie树的过程中，在最后一个结点连接上英语串，trie用个struct数组,多附加一个char[]

另外注意输入格式，空行的问题，(getch, sscanf考虑一下）

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
 
const int maxn = 1e6+5;
struct Trie
{
    char word[11];
    int next[30];
}trie[maxn];
int tot;
int idx(char c){return c - 'a';}
 
void insert(char str[], char s[])
{
    int u = 0, len = strlen(s);
    for(int i = 0; i < len; ++i){
        int c = idx(s[i]);
        if(!trie[u].next[c])    trie[u].next[c] = ++tot;
        u = trie[u].next[c];
    }
    strcpy(trie[u].word, str);
}
 
void findout(char s[])
{
    int u = 0, len = strlen(s);
    for(int i = 0; i < len; ++i){
        int c = idx(s[i]);
        if(!trie[u].next[c]){
            cout << "eh" << '\n';
            return;
        }
        u = trie[u].next[c];
    }
    cout << trie[u].word << '\n';
}
int main()
{
    char s1[12], s2[12], ch[30];
    while(gets(ch)){
        if(ch[0] == 0)  break;
        sscanf(ch,"%s %s", s1, s2);
        insert(s1, s2);
    }
    while(~scanf("%s", s2)){
        findout(s2);
    }
    return 0;
}