小记:题意要读清啊,不然白费一生啊。 一行一行的读,最后以#结束,每一行输出一个结果
思路:放在trie树 练习题的,当然用trie树来解决,遇到一个单词,先在trie树里找是否有,有就继续看下一个单词,没有就放进trie树,然后单词数加1,
每一行数据都定义一颗trie树,处理完一行后delete之,再读入再创建
代码:
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> using namespace std; #define mst(a,b) memset(a,b,sizeof(a)) #define eps 10e-8 const int MAX_ = 10010; const int MAX = 27; const int N = 100010; const int INF = 0x7fffffff; typedef struct Node{ int isStr; struct Node *next[MAX]; Node():isStr(0){ memset(next, NULL, sizeof(next)); } ~Node(){ for(int i = 0;i < MAX; ++i) if(next[i] != NULL) delete next[i]; } }TrieNode,*Trie; Trie root; void Insert(char *s){ TrieNode *p = root,*q; while(*s){ if(p ->next[*s-'a'] == NULL){ q = new TrieNode; p ->next[*s-'a'] = q; } p = p ->next[*s-'a']; s++; } p->isStr = 1; } int find(char *s){ int i = 0; TrieNode *p=root; while(*s){ if(p->next[*s-'a'] == NULL)return i; p = p->next[*s-'a']; s++; } if(p->isStr)i = 1; return i; } int main() { char s[MAX*10], str[MAX*10]; int ans, cnt, len; bool flag; //ans = 0;flag = false;cnt = 0; while(gets(s)&&s[0]!='#'){ root = new TrieNode; ans = 0;flag = false;cnt = 0;len = strlen(s); for(int i = 0; i < len; ++i){ if(s[i] == ' '&& flag){ str[cnt] = '\0'; if(!find(str)){ Insert(str); ans++; } flag = false; cnt = 0; } if(s[i] != ' '){ flag = true; str[cnt++] = s[i]; } } if(cnt){ str[cnt] = '\0'; if(!find(str)){ Insert(str); ans++; } } printf("%d\n",ans); delete root; } }