DEV C++ 程序问题

词链
问题描述
给定一个仅包含小写字母的英文单词表，其中每个单词最多包含50个字母。
如果一张由一个词或多个词组成的表中，每个单词（除了最后一个）都是排在它后面的单词的前缀，则称此表为一个词链。例如下面的单词组成了一个词链：
i
int
integer
而下面的单词不组成词链：
integer
intern
请在给定的单词表中取出一些词，组成最长的词链。最长的词链就是包含单词数最多的词链。
数据保证给定的单词表中，单词互不相同，并且单词按字典顺序排列。
输入(link.in)
第一行一个整数n，表示单词表中单词数
下接n行每行一个单词。
输出(link.out)
一个整数，表示最长词链长度。
样例
link.in link.out
5iintintegerinterninternet 4
数据范围
50%的数据，n<=1000
100%的数据，n<=10000

#include<stdio.h>
#include<string.h>
int len[50000],data[50000];
char d[10010][5000],s[100001];
int can(int a,int b)
{
int i;
for(i=len[b]-1;i>=0;i--)
if(d[a][i]!=d[b][i])
return 0;
return 1;
}
main()
{
int i,j,n,m,max=0,temp=0;
freopen("link.in","r",stdin);
freopen("link.out","w",stdo

关键在于temp等于最大链长度，而max每次都比temp大1
在for循环最后加：
printf("temp=%d\tmax=%d\n", temp, max);
你就明白了

这个写的比较惨，这个复杂度只能过50%数据，我写了个大概跟字典树差不多的，还可以看，起码跑的比较快

#include <cstdio>
#include <cstring>

struct Trie
{
    Trie *next[ 26 ];
    int c;
    void init( )
    {
        int i;
        for ( i = 0; i < 26; i++ )
            next[ i ] = NULL;
        c = 0;
    }
};

Trie *top;
int n, maxn;

void work( )
{
    scanf("%d", &n);
    top = new Trie;
    top->init( );
    char data[ 51 ];
    Trie *p, *t;