校内OJ 1128 词链(link)（Trie+DFS）

1128: 词链(link)

时间限制: 1 Sec  内存限制: 64 MB
提交: 23  解决: 7
[提交][状态][讨论版]

题目描述

给定一个仅包含小写字母的英文单词表，其中每个单词最多包含50个字母。
如果一张由一个词或多个词组成的表中，每个单词（除了最后一个）都是排在它后面的单词的前缀，则称此表为一个词链。例如下面的单词组成了上个词链：
i
int
integer
而下面的单词不组成词链：
integer
intern
请在给定的单词表中取出一些词，组成最长的词链。最长的词链就是包含单词数最多的词链。
数据保证给定的单词表中，单词互不相同。

输入

第1行一个整数(n≤10000)，表示单词表中单词数；
接下来n行，每行一个单词。

输出

一个整数，表示最长词链长度。

样例输入

5

i

integer

internet

intern

int

样例输出

4

本以为用字典树会很麻烦，结果还是挺好写的

用Trie之后DFS一下就行了

代码：

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <sstream>

#include <cstring>

#include <bitset>

#include <string>

#include <deque>

#include <stack>

#include <cmath>

#include <queue>

#include <set>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(x,y) memset(x,y,sizeof(x))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int maxl=55;

const int maxn=26;

struct Trie

{

    Trie *nxt[maxn];

    int cnt;

    Trie()

    {

        cnt=0;

        for (int i=0; i<maxn; ++i)

            nxt[i]=NULL;

    }

};

Trie *L;

char s[maxl];

int ans;

void update(char s[])

{

    int len=strlen(s);

    int indx;

    Trie *cur=L;

    for (int i=0; i<len; ++i)

    {

        indx=s[i]-'a';

        if(!cur->nxt[indx])

        {

            Trie *one=new Trie();

            cur->nxt[indx]=one;

            cur=one;

        }

        else

            cur=cur->nxt[indx];

    }

    ++(cur->cnt);

}

void dfs(Trie *now,int sum)

{

    if(sum>ans)

        ans=sum;

    for (int i=0; i<maxn; ++i)

        if(now->nxt[i]!=NULL)

            dfs(now->nxt[i],sum+now->nxt[i]->cnt);

}

int main(void)

{

    L=new Trie();

    int n;

    scanf("%d",&n);

    while (n--)

    {

        scanf("%s",s);

        update(s);

    }

    ans=0;

    dfs(L,0);

    printf("%d\n",ans);

    return 0;

}