Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // EMaxx.cpp : Defines the entry point for the console application.
- //
- #include "stdafx.h"
- using namespace std;
- const int MAXN = 1e3;
- string word;
- int n;
- struct node
- {
- int l, r, par, link;
- map<char, int> next;
- node(int l = 0, int r = 0, int par = -1)
- : l(l), r(r), par(par), link(-1)
- {
- }
- int len()
- {
- return r - l;
- }
- int &get(char c)
- {
- if (next.count(c) == 0)
- next[c] = -1;
- return next[c];
- }
- };
- node nodes[MAXN];
- int sz;
- struct state
- {
- int v, pos;
- state(int v, int pos) : v(v), pos(pos) {}
- };
- state ptr(0, 0);
- state go(state st, int l, int r)
- {
- while (l < r)
- {
- if (st.pos == nodes[st.v].len())
- {
- st = state(nodes[st.v].get(word[l]), 0);
- if (st.v == -1)
- return st;
- }
- else
- {
- if (word[nodes[st.v].l + st.pos] != word[l])
- return state(-1, -1);
- if (r - l < nodes[st.v].len() - st.pos)
- return state(st.v, st.pos + r - l);
- l += nodes[st.v].len() - st.pos;
- st.pos = nodes[st.v].len();
- }
- }
- return st;
- }
- int split(state st)
- {
- if (st.pos == nodes[st.v].len())
- return st.v;
- if (st.pos == 0)
- return nodes[st.v].par;
- node v = nodes[st.v];
- int id = sz++;
- nodes[id] = node(v.l, v.l + st.pos, v.par);
- nodes[v.par].get(word[v.l]) = id;
- nodes[id].get(word[v.l + st.pos]) = st.v;
- nodes[st.v].par = id;
- nodes[st.v].l += st.pos;
- return id;
- }
- int get_link(int v)
- {
- if (nodes[v].link != -1)
- return nodes[v].link;
- if (nodes[v].par == -1)
- return 0;
- int to = get_link(nodes[v].par);
- state tmp = go(state(to, nodes[to].len()), nodes[v].l + (nodes[v].par == 0), nodes[v].r);
- return nodes[v].link = split(tmp);
- }
- void tree_extend(int pos)
- {
- for (;;)
- {
- state nptr = go(ptr, pos, pos + 1);
- if (nptr.v != -1)
- {
- ptr = nptr;
- return;
- }
- int mid = split(ptr);
- int leaf = sz++;
- nodes[leaf] = node(pos, n, mid);
- nodes[mid].get(word[pos]) = leaf;
- ptr.v = get_link(mid);
- ptr.pos = nodes[ptr.v].len();
- if (!mid)
- break;
- }
- }
- void build_tree()
- {
- sz = 1;
- for (int i = 0; i < n; ++i)
- tree_extend(i);
- }
- void NodeGraph(int num, string &sb)
- {
- if (nodes[num].par != -1)
- {
- size_t len = nodes[num].len();
- string str = word.substr(nodes[num].l, len);
- sb.append("node")
- .append(std::to_string(nodes[num].par))
- .append(" -> node")
- .append(std::to_string(num))
- .append("[label=\"")
- .append(str)
- .append("\", weight=3,color=black,size=11]\n");
- }
- if (nodes[num].link != -1)
- {
- sb.append("node")
- .append(std::to_string(num))
- .append(" -> node")
- .append(std::to_string(nodes[num].link))
- .append("[label=\"\", weight=.01,style=dotted]\n");
- }
- }
- string WriteDotGraph()
- {
- string sb;
- sb.append("digraph {\n");
- sb.append("rankdir = LR;\n");
- sb.append("edge [arrowsize=0.5,fontsize=11];\n");
- for (size_t i = 0; i < sz; i++)
- {
- string num = std::to_string(i);
- string tmp = "node";
- tmp.append(num)
- .append(" [label=\"")
- .append(num)
- .append("\",style=filled,fillcolor=yellow,"
- "shape=circle,width=.1,height=.1,fontsize=11,margin=0.01];\n");
- sb.append(tmp);
- NodeGraph(i, sb);
- }
- sb.append("}\n");
- return sb;
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- word = "aabaabbc";
- n = word.length();
- build_tree();
- fstream fs;
- fs.open("D:\\Temp\\graph.gv", fstream::out);
- fs << WriteDotGraph();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment