PKU 1997 Word Puzzle

http://poj.org/problem?id=1997
r×c個の英小文字とk個のキーワードが与えられる。
r×cの中で8方向を見て、キーワードが見つかればそれを最終局面から除外する。
残った文字を全て出力せよというような問題。

25サブミット目にしてようやくAC。
最初は愚直にやると流石に間に合わなさそうと思い、よく考えるとハッシュゲーかなとか考えて実装しました。
が、どんなに高速化してもTLE。
O(200*200*20*8*20)*テストケースぐらいだから、間に合いそうな気がしたんですけどね。
仕方ないので、あきらめよかとも思いましたが、せっかく書いたコードを消すのもためらわれたのでdiscussに何か書いてないかと思い覗いてみると、trieの文字があったのでせっかくなので書いてみようと思い立ちました。
最後らへんはTLEがWAになっていて、詰んだかと思いましたが、tx,tyの中身が間違っていて、そこを直したらなんとかなったので良かったです。

問題番号で検索かけても他の国の人も誰も答えを貼りつけていないものを解けたのですごく満足できました。
追記：しっかり検索かけたら普通に解いている人いました。

typedef struct _node{
  _node* next[26];
  bool end;
}node;

node*trie[200000];
node*root;
node ent[200000];
int sz;

int app(const char*in){
  int idx=0;
  int ret=0;
  node*p;
  for(p=root->next[in[idx]-'a'];p;p=p->next[in[idx]-'a']){

    ++idx;
    if(p->end)ret=idx;
    if(in[idx]==0)break;
  }

  return ret;
}

void insert(char*in){
  node* p=root;
  for(;*in;++in){
    if(p->next[*in-'a']==NULL){
      p->next[*in-'a']=ent+sz++;
    }
    p=p->next[*in-'a'];    
  }
  p->end=true;
}

int r,c;
int k;
char*in[200];
bool sc[200][200];
char word[100];

int tx[]={0,1,1,1,0,-1,-1,-1},ty[]={1,1,0,-1,-1,-1,0,1};

inline void elm(int x,int y){
  rep(i,8){
    int cx=x,cy=y;
    rep(j,20){
      word[j]=in[cx][cy];
      cx+=tx[i];
      cy+=ty[i];
      if(cx<0)cx+=r;
      if(cx>=r)cx-=r;
      if(cy<0)cy+=c;
      if(cy>=c)cy-=c;
    }
    cx=x,cy=y;
    word[20]=0;

    int er=app(word);

    rep(j,er){
      sc[cx][cy]=true;

      cx+=tx[i];
      cy+=ty[i];
      if(cx<0)cx+=r;
      if(cx>=r)cx-=r;
      if(cy<0)cy+=c;
      if(cy>=c)cy-=c;      
    }

  }
}

char ans[50000];

char input[7000*1024];
char*pos;

int getnum(){
  int ret=0,c;
  while(!isdigit(c=*pos++));
  ret=c&15;
  while(isdigit(c=*pos))ret=(ret<<3)+(ret<<1)+(c&15),++pos;
  return ret;
}

char * getstr(){
  char *ret;
  while(!isalpha(*pos))++pos;
  ret=pos;
  while(isalpha(*pos))++pos;
  *pos=0;
  return ret;
}

main(){

  fread(input,sizeof(input),1,stdin);

  pos=input;
  int T=getnum();

  while(T--){
    memset(trie,0,sizeof(trie));
    memset(sc,0,sizeof(sc));
    memset(ent,0,sizeof(ent));
    sz=0;
    root=ent+sz++;

    r=getnum();
    c=getnum();
    rep(i,r)in[i]=getstr();
    int k=getnum();

    rep(i,k)
      insert(getstr());

    rep(i,r)rep(j,c)elm(i,j);
    int as=0;
    rep(i,r)rep(j,c)if(!sc[i][j])ans[as++]=in[i][j];
    ans[as++]='\n';
    ans[as]=0;
    printf(ans);
  }
}