Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 我的字典树有点慢诶 ， 47ms

Posted by jufusong at 2013-03-20 15:28:41 on Problem 2001
```# include <cstdio>
# include <iostream>
# include <set>
# include <map>
# include <vector>
# include <list>
# include <queue>
# include <stack>
# include <cstring>
# include <string>
# include <cstdlib>
# include <cmath>
# include <algorithm>

using namespace std ;

char s [ 1100 ] [ 21 ] ;

struct Dic
{
int time ;
int next [ 30 ] ;
} dic [ 1000000 ] ;
int cnt ;

void addword ( char * s )
{
int len = strlen ( s ) ;
int num = 0 ;
for ( int i = 0 ; i < len ; i ++ )
{
int c =  s [ i ] - 'a' ;
if ( dic [ num ] . next [ c ] )
{
num = dic [ num ] . next [ c ] ;
dic [ num ] . time ++ ;
}
else
{
dic [ num ] . next [ c ] = cnt ;
num = cnt ++ ;
dic [ num ] . time ++ ;
}
}
}

void findword ( char * s )
{
int len = strlen ( s ) ;
int num = 0 ;
for ( int i = 0 ; i < len ; i ++ )
{
int c =  s [ i ] - 'a' ;
if ( dic [ num ] . time == 1 )
break ;
putchar ( s [ i ] ) ;
num = dic [ num ] . next [ c ] ;
}
}

int main ( )
{
cnt = 1 ;
int n = 0 ;
while ( gets ( s [ n ] ) )
{
addword ( s [ n ++ ] ) ;
}
dic [ 0 ] . time = n ;
for ( int i = 0 ; i < n ; i ++ )
{
printf ( "%s " , s [ i ] ) ;
findword ( s [ i ] ) ;
printf ( "\n" ) ;
}
}```

Followed by: