rendered paste body/* Author :Ravi Shankar.T */#include <iostream>#include <fstream>#include <cstring>#include <string>#include <list>#include <cctype>#include <cassert>using namespace std;#define REP(i,n) for(int i=0;i<(n);++i)#define FOR(i,a,b) for(int i=(a);i<=(b);++i)#define FORD(i,a,b) for(int i=(a);i>=(b);--i)#define FIT(i,c,t) for(t::iterator i=(c).begin();i!=(c).end();++i)#define SET(arr,val) memset((arr),(val),sizeof(arr))typedef list<string> L_S;const int CHSZ=27;class Node { public: Node () // next[0] used to specify if this Node is the End of a word { REP (i, CHSZ) next[i] = NULL; } Node *insert (int ch) { assert(isalpha(ch) || ch=='\0'); if (ch!='\0') ch = ch-'a'+1; // Convert it into a index for next if (next[ch] == NULL) next[ch] = new Node; return next[ch]; } Node *insert (const char *inp) { Node *trie = this; for (int i=0; inp[i]; ++i) trie = trie->insert(inp[i]); trie->insert('\0'); return trie; } void print(string prefix="") { for (int i=0; i<CHSZ; ++i) { if (this->next[i]) { if (i!=0) (this->next[i])->print(prefix+((char)('a'-1+i))); else cout<<prefix<<endl; } } } private: char ch; Node *next[CHSZ]; friend bool is_composite_word ( Node *trie, int M, const char *inp);};bool is_composite_word ( Node *head, int M, const char *inp){ if (M<0) M=0; Node *trie; while(*inp) { trie = trie->next[*inp]; ++inp; if (trie) return false; if (trie->next[0]) { if (is_composite_word (head, M-1, inp)) return true; } } if (*inp && M==0 && trie->next[0]) return true; return false;} int main (int argc, char *argv[]){ Node trie; L_S inp_list; string tmp; ifstream fin(argv[1]); while ( getline(fin, tmp) ) { if (tmp.size() < 3) continue; inp_list.push_back(tmp); trie.insert (tmp.c_str()); } int M; sscanf (argv[2], "%d", &M); int composite_word_count = 0; if (is_composite_word(&trie, M, "abcdefghi")) ++composite_word_count; /* FIT (it, inp_list, L_S) { cout<<*it<<endl; if (is_composite_word(&trie, M, it->c_str())) ++composite_word_count; } */ cout<<composite_word_count<<endl; return 0;}