HNU_11704

    这个和POJ的3332十分类似，都是判断一个字符串是否合法，具体怎么想可以参考一下我的另一篇题解，，代码为了看起来思路清晰一些，所以写得就十分啰嗦了，很多地方是可以简化的。

    由于单词很多，如果暴搜判断有无的话时间消耗比较大，不过这个题直接暴搜单词也是过得了的，比较快的方式就是用二分、哈希表、字典树。

    此外这个题目好像给出的noun和verb的长度有的是超过6的，不过如果使用字典树记录的话基本是没有问题的，但用哈希表的话就要注意这个长度的问题了。

#include
     
       #include
      
        #define MAXL 500010 #define MAXD 60010 int N, M, pat; char b[MAXL]; int ntree[MAXD][26], noun[MAXD], ne, vtree[MAXD][26], verb[MAXD], ve; void insert_noun(int cur, int k) {
       ++ ne;     noun[ne] = 0;     memset(ntree[ne], 0, sizeof(ntree[ne]));     ntree[cur][k] = ne; } void insert_verb(int cur, int k) {
       ++ ve;     verb[ve] = 0;     memset(vtree[ve], 0, sizeof(vtree[ve]));     vtree[cur][k] = ve; } void init() {
   int i, j, k, cur;     ne = ve = 0;     noun[ne] = verb[ve] = 0;     memset(ntree[ne], 0, sizeof(ntree[ne]));     memset(vtree[ve], 0, sizeof(vtree[ve])); for(i = 0; i < N; i ++)     {
           gets(b);         cur = 0; for(j = 0; b[j]; j ++)         {
               k = b[j] - 'a'; if(!ntree[cur][k])                 insert_noun(cur, k);             cur = ntree[cur][k];         }         noun[cur] = 1;     } for(i = 0; i < M; i ++)     {
           gets(b);         cur = 0; for(j = 0; b[j]; j ++)         {
               k = b[j] - 'a'; if(!vtree[cur][k])                 insert_verb(cur, k);             cur = vtree[cur][k];         }         verb[cur] = 1;     } } void delblank(int &i) {
   while(b[i] == ' ')         ++ i; } void delword(int &i) {
   while(b[i] && b[i] != ' ')         ++ i; } int find_and(int i) {
   if(b[i] == 'a' && b[i + 1] == 'n' && b[i + 2] == 'd' && b[i + 3] == ' ') return 1; return 0; } int find_comma(int i) {
   if(b[i] == ',') return 1; return 0; } void pattern(int i) {
   if(pat == 0)     {
           pat = 1;     } else if(pat == 1)     {
           pat = 2;     } else if(pat == 2)     {
   if(find_and(i))             pat = 3; else             pat = 4;     } else if(pat == 3)     {
           pat = 2;     } else if(pat == 4)     {
           pat = 5;     } else if(pat == 5)     {
   if(find_and(i))             pat = 6; else if(find_comma(i))             pat = 7; else             pat = 8;     } else if(pat == 6)     {
           pat = 5;     } else if(pat == 7)     {
           pat = 2;     } else if(pat == 8)     {
           pat = 9;     } } int find_noun(int i) {
   int k, cur;     cur = 0; for(; b[i] && b[i] != ' '; ++ i)     {
           k = b[i] - 'a'; if(!ntree[cur][k]) return 0;         cur = ntree[cur][k];     } return noun[cur]; } int find_verb(int i) {
   int k, cur;     cur = 0; for(; b[i] && b[i] != ' '; ++ i)     {
           k = b[i] - 'a'; if(!vtree[cur][k]) return 0;         cur = vtree[cur][k];     } return verb[cur]; } int find_fix(int i) {
   if(b[i] != '[') return 0; for(; b[i] && b[i] != ' '; ++ i); if(b[i - 1] != ']') return 0; return 1; } int check(int i) {
   if(pat == 1)     {
   if(find_fix(i)) return 1; else return 0;     } else if(pat == 2)     {
   if(find_noun(i)) return 1; else return 0;     } else if(pat == 3)     {
   if(find_and(i)) return 1; else return 0;     } else if(pat == 4)     {
   if(find_verb(i)) return 1; else return 0;     } else if(pat == 5)     {
   if(find_noun(i)) return 1; else return 0;     } else if(pat == 6)     {
   if(find_and(i)) return 1; else return 0;     } else if(pat == 7)     {
   if(find_comma(i)) return 1; else return 0;     } else if(pat == 8)     {
   if(find_fix(i)) return 1; else return 0;     } return 0; } int solve() {
   int i, j, k;     gets(b);     pat = 0; for(i = 0, delblank(i); b[i];)     {
           pattern(i); if(!check(i)) return 0;         delword(i);         delblank(i);     } if(pat == 8) return 1; else return 0; } int main() {
   while(gets(b) != NULL)     {
           sscanf(b, "%d%d", &N, &M);         init(); if(solve())             printf("a good title\n"); else             printf("a bad title\n");     } return 0; }