字典树水题几枚

1.HDU 1251 统计难题

很裸的一道字典树，直接输出个数的， 其实用map也能水过，只不过效率有些低

map版本

map做法就是把每个字符串的所有前缀遍历一遍，然后存起来，最后直接数个数就行。

具体代码吐下 很久很久以前的代码 很挫

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
char s[11];
int main()
{
    map<string,int>mp;
    int i;
    while(gets(s))
    {

        int len=strlen(s);
        if(!len)
        break;
        string a="";
        for(i=0;i<len;i++)
        {
            a=a+s[i];
            mp[a]++;
        }
    }
    char ss[11];
    while(scanf("%s",ss)!=EOF)
    {
        string tmp=ss;
        printf("%d\n",mp[tmp]);
    }
    return 0;
}

然后是字典树版本的， 刚写的，略挫

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 100000000
#define PI acos(-1.0)
using namespace std;
char str[12];
struct trie
{
    int num;
    trie *next[26];
    trie()
    {
        num = 0;
        for(int i = 0; i < 26; i++)
        next[i] = 0;
    }
} *root, temp[500005]; // 为了避免用new太多浪费时间，事先开好一个数组， 当然，内存又有可能爆掉了
int ncount = 0;
void insert(trie *p, char *s)
{
    int ix = 0;
    p ->num++;
    while(s[ix])
    {
        int nx = s[ix] - 'a';
        if(p -> next[nx])
        {
            p = p -> next[nx];
            ix++;
        }
        else
        {
            p -> next[nx] = &temp[ncount++]; //直接取址
            p = p -> next[nx];
            ix++;
        }
        p -> num++;
    }
}
int find(trie *p, char *s)
{
    int ix = 0, ans;
    while(s[ix])
    {
        int nx = s[ix] - 'a';
        if(p -> next[nx])
        {
            p = p -> next[nx];
            ans = p -> num;
            ix++;
        }
        else return 0;
    }
    return ans;
}
int main()
{
    //freopen("ride.in","r",stdin);
    //freopen("ride.out","w",stdout);
    root = new trie;
    while(gets(str))
    {
        if(strlen(str) == 0) break;
        insert(root, str);
    }
    while(scanf("%s", str) != EOF)
    {
        printf("%d\n", find(root, str));
    }
    return 0;
}

2.POJ 2001Shortest Prefixes

同样，很裸的字典树。

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define PI acos(-1.0)
using namespace std;
char s[1005][23];
struct trie
{
    int num;
    trie *next[26];
    trie()
    {
        num = 0;
        for(int i = 0; i < 26; i++)
        next[i] = NULL;
    }
}*root, temp[50000];
int ncount = 0;
void insert(trie *p, char *s)
{
    int ix = 0;
    p -> num++;
    while(s[ix])
    {
        int nx = s[ix] - 'a';
        if(p -> next[nx])
        {
            p = p -> next[nx];
            ix++;
        }
        else
        {
            p -> next[nx] = &temp[ncount++]; //直接取址
            p = p -> next[nx];
            ix++;
        }
        p -> num++;
    }
}
int find(trie *p, char *s)
{
    int ix = 0, ans;
    while(s[ix])
    {
        int nx = s[ix] - 'a';
        if(p -> next[nx])
        {
            p = p -> next[nx];
            ans = p -> num;
            ix++;
        }
        else return 0;
    }
    return ans;
}
int main()
{
    //freopen("ride.in","r",stdin);
    //freopen("ride.out","w",stdout);
    int cnt = 0, i, j;
    root = new trie;
    while(scanf("%s", s[cnt++]) != EOF)
    {
        insert(root, s[cnt - 1]);
    }
    for(i = 0; i < cnt; i++)
    {
        int len = strlen(s[i]);
        char tp[23];
        for(j = 0; j < 21; j++)
        tp[j] = '\0';
        int ct = 0;
        for(j = 0; j < len; j++)
        {
            tp[ct++] = s[i][j];
            if(find(root, tp) == 1)
            {
                break;
            }
        }
        printf("%s %s\n", s[i], tp);
    }
    return 0;
}