HDU 1251 统计难题字符匹配

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目描述：先说明此题只有一个测试实例，然后输入一系列的单词，以一个回车为结束符，然后输入一个字符串，要你查找以这个字符串为前缀的单词的个数，处理到文件结束。

解题报告：一开始看到这题，竟然直接用暴力去解了，根本没有想到用字典树，因为字典树是很久以前学的了，刚学的时候一个题都没做，所以现在都忘了，还好这题一次就写出来了，还没有调试，用字典树，要注意的是，一般字典树是在每个点标记有没有以这个点没结束的单词，但是这里要将每个节点标记的成经过这个节点的次数，因为可能有多个单词的前缀相同，这样就会多次经过这个点，如果只标记是否走过的话，就没有办法统计次数了。代码附上：

 #include<cstdio>

 #include<cstring>

 typedef struct node {

     char c;

     int flag;

     node *next[];

     node() {         //各种初始化

         flag = ;

         for(int i = ;i<;++i)

         next[i] = NULL;

     }

 }Trie;

 void push(Trie *head,char *s) {    //插入字符串

     int len = strlen(s);

     Trie *p = head;

     for(int i = ;i<len;++i) {

         if(p->next[s[i]-'a'] == NULL) {

             p->next[s[i]-'a'] = new Trie;

             p->next[s[i]-'a']->c = s[i];

             p->next[s[i]-'a']->flag++;   //这里要注意因为插入的字符串前缀相同的可能有多个，所以应该统计个数，而不是标记是否存在

             p = p->next[s[i]-'a'];

         }

         else if(p->next[s[i]-'a'] != NULL) {

             p->next[s[i]-'a']->flag++;

             p = p->next[s[i] -'a'];

         }

     }

 }

 int serch(Trie *head,char *s) {

      int len = strlen(s);

      Trie *p = head;

      for(int i = ;i<len;++i) {

          if(p->next[s[i]-'a'] == NULL)

          return ;    //不能走到末尾的字符，直接返回0;

          else p = p->next[s[i]-'a'];

          if(i == len-)

          return p->flag;

      }

 }

 void Delete(Trie *head) {

     Trie *p = head;

     for(int i = ;i<;++i) {

         if(p->next[i] != NULL)

         p = p->next[i];

         else {

             delete p;

             return ;

         }

     }

 }

 int main() {

     Trie *head = new Trie;

     char s[];

     while(gets(s))

     if(s[] != NULL)

     push(head,s);

     else break;

     while(scanf("%s",s)!=EOF)

     printf("%d\n",serch(head,s));

     Delete(head);       //清理内存

     return ;

 }