PKU : 3193 - Cow Phrasebook
問題概要
http://poj.org/problem?id=3193
N個の文字列が入力されます.
さらに, M個の文字列が順番に入力されます.
M個の文字列の中で, N個の文字列の方の接頭辞となるような文字列が, いくつ存在するか答えてください.
アルゴリズム
おそらく, 単純に全探索すると, TLEしそうだと思ったので, Trie使いました.
どうにか解けました.
Trie使っても, 0.5秒程度かかったので, あきらかに全探索では通らないでしょう.
プログラム
Trieのコードは, スパゲッティソースから引用しています.
struct Trie{ int value; Trie *next[0x100]; Trie(){fill(next,next+0x100,(Trie*)0);} }; void find(char *t,Trie *r){ for(int i=0;t[i];i++){ char c = t[i]; if(!r->next[c]) r->next[c] = new Trie; r = r->next[c]; } } bool find2(char *t,Trie *r){ for(int i=0;t[i];i++){ char c = t[i]; if(!r->next[c]) return false; r = r->next[c]; } return true; } int main(void){ Trie t; int n,m; scanf(" %d%d ",&n,&m); rep(i,n){ char s[100]; fgets(s,100,stdin); s[strlen(s)-1] = 0; find(s,&t); } int ans = 0; rep(i,m){ char s[100]; fgets(s,100,stdin); s[strlen(s)-1] = 0; if(find2(s,&t)) ans++; } printf("%d\n",ans); }