Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我的字典树有点慢诶 , 47ms# 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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator