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);
}