字典树水题几枚

java-mans

浏览: 11429456 次

最近访客更多访客>>

morelily

devcang

serisboy

chjinniu

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (15568)

社区版块

存档分类

2012-08 ( 1467)
2012-07 ( 1872)
2012-06 ( 1125)
更多存档...

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;
}

3. HDU 1247

这个就当做模板吧。。。

字典树应用，先插入所有单词，然后暴力拆分每个单词，看拆分后的两个单词是否都在字典树中出现，注意是确切出现，而不是作为子串出现，所以插入的时候注意下

/*
ID: CUGB-wwj
PROG:
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[50051][50];
struct trie
{
    int num;
    trie *next[26];
    trie()
    {
        num = 0;
        for(int i = 0; i < 26; i++)
        next[i] = NULL;
    }
} *root ;
int ncount = 0;
void insert(trie *p, char *s)
{
    int ix = 0;
    while(s[ix])
    {
        int nx = s[ix] - 'a';
        if(p -> next[nx] == NULL)
            p -> next[nx] = new trie();
        p = p -> next[nx];
        ix++;
    }
    p -> num++;
}
int find(trie *p, char *s)
{
    int ix = 0, ans = 0;
    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()
{
    root = new trie();
    while(scanf("%s", str[ncount++]) != EOF)
    {
        insert(root, str[ncount - 1]);
    }
    for(int i = 0; i < ncount; i++)
    {
        int len = strlen(str[i]);
        int flag = 0;
        for(int j = 1; j < len; j++)
        {
            char ta[22], tb[22];
            memset(ta, '\0', sizeof(ta));
            memset(tb, '\0', sizeof(tb));
            int cnt1 = 0, cnt2 = 0;
            for(int k = 0; k < j; k++)
                ta[cnt1++] = str[i][k];
            for(int k = j; k < len; k++)
                tb[cnt2++] = str[i][k];
            if(find(root, ta) && find(root, tb))
            {
                flag = 1;
                break;
            }
        }
        if(flag) puts(str[i]);
    }
    return 0;
}

分享到：