Veikedo

Untitled

Dec 5th, 2013
401
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.39 KB | None | 0 0
  1. // EMaxx.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include "stdafx.h"
  5. using namespace std;
  6.  
  7. const int MAXN = 1e3;
  8. string word;
  9. int n;
  10.  
  11. struct node
  12. {
  13.     int l, r, par, link;
  14.     map<char, int> next;
  15.  
  16.     node(int l = 0, int r = 0, int par = -1)
  17.         : l(l), r(r), par(par), link(-1)
  18.     {
  19.     }
  20.  
  21.     int len()
  22.     {
  23.         return r - l;
  24.     }
  25.  
  26.     int &get(char c)
  27.     {
  28.         if (next.count(c) == 0)
  29.             next[c] = -1;
  30.  
  31.         return next[c];
  32.     }
  33. };
  34. node nodes[MAXN];
  35. int sz;
  36.  
  37. struct state
  38. {
  39.     int v, pos;
  40.     state(int v, int pos) : v(v), pos(pos)  {}
  41. };
  42. state ptr(0, 0);
  43.  
  44. state go(state st, int l, int r)
  45. {
  46.     while (l < r)
  47.     {
  48.         if (st.pos == nodes[st.v].len())
  49.         {
  50.             st = state(nodes[st.v].get(word[l]), 0);
  51.             if (st.v == -1)
  52.                 return st;
  53.         }
  54.         else
  55.         {
  56.             if (word[nodes[st.v].l + st.pos] != word[l])
  57.                 return state(-1, -1);
  58.  
  59.             if (r - l < nodes[st.v].len() - st.pos)
  60.                 return state(st.v, st.pos + r - l);
  61.  
  62.             l += nodes[st.v].len() - st.pos;
  63.             st.pos = nodes[st.v].len();
  64.         }
  65.     }
  66.  
  67.     return st;
  68. }
  69.  
  70. int split(state st)
  71. {
  72.     if (st.pos == nodes[st.v].len())
  73.         return st.v;
  74.  
  75.     if (st.pos == 0)
  76.         return nodes[st.v].par;
  77.  
  78.     node v = nodes[st.v];
  79.     int id = sz++;
  80.  
  81.     nodes[id] = node(v.l, v.l + st.pos, v.par);
  82.     nodes[v.par].get(word[v.l]) = id;
  83.     nodes[id].get(word[v.l + st.pos]) = st.v;
  84.     nodes[st.v].par = id;
  85.     nodes[st.v].l += st.pos;
  86.  
  87.     return id;
  88. }
  89.  
  90. int get_link(int v)
  91. {
  92.     if (nodes[v].link != -1)
  93.         return nodes[v].link;
  94.  
  95.     if (nodes[v].par == -1)
  96.         return 0;
  97.  
  98.     int to = get_link(nodes[v].par);
  99.  
  100.     state tmp = go(state(to, nodes[to].len()), nodes[v].l + (nodes[v].par == 0), nodes[v].r);
  101.     return nodes[v].link = split(tmp);
  102. }
  103.  
  104. void tree_extend(int pos)
  105. {
  106.     for (;;)
  107.     {
  108.         state nptr = go(ptr, pos, pos + 1);
  109.         if (nptr.v != -1)
  110.         {
  111.             ptr = nptr;
  112.             return;
  113.         }
  114.  
  115.         int mid = split(ptr);
  116.         int leaf = sz++;
  117.  
  118.         nodes[leaf] = node(pos, n, mid);
  119.         nodes[mid].get(word[pos]) = leaf;
  120.  
  121.         ptr.v = get_link(mid);
  122.         ptr.pos = nodes[ptr.v].len();
  123.  
  124.         if (!mid)
  125.             break;
  126.     }
  127. }
  128.  
  129. void build_tree()
  130. {
  131.     sz = 1;
  132.     for (int i = 0; i < n; ++i)
  133.         tree_extend(i);
  134. }
  135.  
  136. void NodeGraph(int num, string &sb)
  137. {
  138.     if (nodes[num].par != -1)
  139.     {
  140.         size_t len = nodes[num].len();
  141.         string str = word.substr(nodes[num].l, len);
  142.  
  143.         sb.append("node")
  144.             .append(std::to_string(nodes[num].par))
  145.             .append(" -> node")
  146.             .append(std::to_string(num))
  147.             .append("[label=\"")
  148.             .append(str)
  149.             .append("\", weight=3,color=black,size=11]\n");
  150.     }
  151.  
  152.     if (nodes[num].link != -1)
  153.     {
  154.         sb.append("node")
  155.             .append(std::to_string(num))
  156.             .append(" -> node")
  157.             .append(std::to_string(nodes[num].link))
  158.             .append("[label=\"\", weight=.01,style=dotted]\n");
  159.     }
  160. }
  161.  
  162.  
  163. string WriteDotGraph()
  164. {
  165.     string sb;
  166.     sb.append("digraph {\n");
  167.     sb.append("rankdir = LR;\n");
  168.     sb.append("edge [arrowsize=0.5,fontsize=11];\n");
  169.  
  170.     for (size_t i = 0; i < sz; i++)
  171.     {
  172.         string num = std::to_string(i);
  173.  
  174.         string tmp = "node";
  175.         tmp.append(num)
  176.             .append(" [label=\"")
  177.             .append(num)
  178.             .append("\",style=filled,fillcolor=yellow,"
  179.             "shape=circle,width=.1,height=.1,fontsize=11,margin=0.01];\n");
  180.  
  181.         sb.append(tmp);
  182.  
  183.         NodeGraph(i, sb);
  184.     }
  185.  
  186.     sb.append("}\n");
  187.     return sb;
  188. }
  189.  
  190.  
  191. int _tmain(int argc, _TCHAR* argv[])
  192. {
  193.     word = "aabaabbc";
  194.     n = word.length();
  195.  
  196.     build_tree();
  197.  
  198.     fstream fs;
  199.     fs.open("D:\\Temp\\graph.gv", fstream::out);
  200.     fs << WriteDotGraph();
  201.  
  202.     return 0;
  203. }
Advertisement
Add Comment
Please, Sign In to add comment