Marcadian’s Blog

Soal Trie lagi, kali ini diminta sequence katanya.Problem

#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

typedef struct
{
 char kar;
 bool isWord;
 int parent;
 map<char,int> child;
}node;

char s[100];
node tree[2000001];
int idx;
int len;
int nn, ma;
void insert(int nodeIdx, int charIdx)
{
 if (tree[nodeIdx].child.count(s[charIdx])==0)
 {
  tree[++idx].kar = s[charIdx];
  tree[idx].parent = nodeIdx;
  tree[idx].child.clear();
  tree[nodeIdx].child[s[charIdx]] = idx;
 }
 if (charIdx==len-1) tree[tree[nodeIdx].child[s[charIdx]]].isWord = 1;
 else
 insert(tree[nodeIdx].child[s[charIdx]], charIdx+1);
}

void traverse(int x,int depth)
{
 map<char,int>::iterator i;
 depth+=tree[x].isWord;
 if (ma < depth)
 {
  ma = depth;
  nn = x;
 }
 for(i=tree[x].child.begin();i!=tree[x].child.end();i++)
  traverse(i->second,depth);
}

int main()
{
 idx = 0;
 tree[0].kar=0;
 ma=-1;
 while (scanf("%s",s))
 {
  if (strcmp(s,".")==0) break;
  len = strlen(s);
  insert(0,0);
 }
 nn=0;
 traverse(0,0);
 int  res[100];
 char ss[100];
 int dd=0;
 while (nn)
 {
  ss[dd]= tree[nn].kar;
  res[dd] = tree[nn].isWord;
  dd++;
  nn = tree[nn].parent;
 }
 reverse(ss,ss+dd);
 reverse(res,res+dd);
 ss[dd] = 0;

 for(int i=0;i<dd;i++)
 {
  if (res[i])
  {
   char temp = ss[i+1];
   ss[i+1] = 0;
   printf("%s\n",ss);
   ss[i+1] = temp;
  }
 }
 return 0;
}