[字典树]hihocoder 1366 逆序单词

描述

在英文中有很多逆序的单词，比如dog和god，evil和live等等。

现在给出一份包含N个单词的单词表，其中每个单词只出现一次，请你找出其中有多少对逆序单词。

输入

第1行：1个整数，N，表示单词数量。2≤N≤50,000。

第2..N+1行：每行1个单词，只包含小写字母，每个单词长度不超过16个字母。保证每个单词只出现一次，且不会出现回文单词（即一个单词倒序还是它自己，比如eye）。

输出

第1行：1个整数，表示单词表中逆序单词的对数。

样例输入

6
dog
live
hiho
evil
coder
god

样例输出

2

//hiho1366
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALTN 26
char op[20];

typedef struct _Node{
   int flag;
   struct _Node *nxt[ALTN];
}Node;

Node *root;

void init_node(Node *tmp)
{
   int i;
   for(i=0;i<ALTN;i++){
      tmp->nxt[i]=NULL;
      tmp->flag=0;
   }
}

void insert_node(char *s)
{
   Node* tNode;
   int i;
   int to;
   int len=strlen(s);
   Node *now=root;
   for(i=len-1;i>=0;i--){
      to=s[i]-'a';
      if(now->nxt[to] == NULL){
         tNode=(Node*)malloc(sizeof(Node));
         init_node(tNode);
         now->nxt[to] = tNode;
      }
      now=now->nxt[to];
   }
   now->flag++;
}

int fid(char *s)/* find in dictionary */
{
   int len=strlen(s);
   int i;
   int to;
   Node *now=root;
   for(i=0;i<len;i++){
      to=s[i]-'a';
      if(now->nxt[to]==NULL)
         return 0;
      now=now->nxt[to];
   }
   return now->flag;
}

int main(int argc, char* argv[])
{
   int n;
   if(NULL==freopen("hihocoder1366i.txt","r",stdin))
      return -1;

   root = (Node *)malloc(sizeof(Node));/*开始我把这两行放外面, 编译错误*/
   init_node(root);/*函数调用不能放在外部的, 否则会被认为是重复定义*/

   int ans=0;
   scanf("%d", &n);
   //getchar();//什么用不清楚
   for(int i=0;i<n;i++){
      scanf("%s",op);/*读入字符串*/

      ans+=fid(op);/*正序查询字符串*/

      insert_node(op);/*逆序插入字符串*/

      memset(op,0,sizeof(op));
   }
   printf("%d\n",ans);
   return 0;
}

在VS2005中生成时出错：error C4430: missing type specifier - int assumed. Note: C++ does not support default-int

这是因为在VC6中，如果没有显示的指定返回值类型，编译器将其视为默认整型。但是vs2005不支持默认整型。

解决方法如下：
打开：项目----项目属性----配置属性----C/C++----命令行，在附加选项那里添加/wd4430这个选项。

第一绿茶；第二红葡萄酒；第三豆浆；第四酸奶；第五骨头汤；第六蘑菇汤。
 
这是我以前的写的，现在我要说最好的饮品不是别的， 而是最普通的白开水。

“大羹无味，实则至味”——2012-07-31