Ideone.com

fork download

copy

using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
 
namespace PMS.Common.Collections
{
    // Abstract Suffix Tree class. Defines interface for different implementations of
    // suffix tree construction algorithms and internal representations
    //
    // Usage example:
    //        var tree = SuffixTree.Build("cacao", SuffixTreeAlgorithm.UkkonenLinear);
    //        var matches = tree.Match("ca").ToArray();
    //        Console.WriteLine(tree.ToDotNotation());
    //
    // Dot notation can be rendered here: http://w...content-available-to-author-only...z.com
    public abstract class SuffixTree
    {
        #region Fields
        protected static char TerminationCharacter = '$';
        #endregion
 
        #region Api
        public abstract bool IsMatch(string substring);
 
        public abstract IEnumerable<int> Match(string substring);
 
        public abstract string ToDotNotation();
        #endregion
 
        #region Construction
        public static SuffixTree Build(string text, SuffixTreeAlgorithm algorithm)
        {
            if (text ==  null)
            {
                throw new ArgumentNullException(nameof(text));
            }
 
            if (text.Contains(TerminationCharacter))
            {
                throw new ArgumentException("Input contains termination character", nameof(text));
            }
 
            switch (algorithm)
            {
                case SuffixTreeAlgorithm.UkkonenLinear: // O(n)
                    return new SuffixTreeUkkonenLinear(text);
 
                default:
                    throw new NotImplementedException($"No implementation for algoritm {algorithm}");
            }
        }
        #endregion
    }
 
    public enum SuffixTreeAlgorithm
    {
        NaiveUsingTrie,
        Naive,
        UkkonenCubic,
        UkkonenQuadratic,
        UkkonenLinear,
        UkkonenFast,
        Weiner,
        McCreight
    }
 
    /// <summary>
    /// Ukkonen linear time O(n) algorithm
    /// As described in the book by D. Gusfield, Algorithms on Strings, Trees and Sequences
    /// </summary>
    public class SuffixTreeUkkonenLinear : SuffixTree
    {
        #region Fields
        private static readonly int currentPosition = int.MinValue;
 
        private readonly Node root;
        private readonly string text;
        #endregion
 
        #region Constructor
        public SuffixTreeUkkonenLinear(string inputText)
        {
            text = inputText + TerminationCharacter;
            root = Build(text);
        }
        #endregion
 
        #region Api
        public override bool IsMatch(string substring)
        {
            return Match(substring).Any();
        }
 
        public override IEnumerable<int> Match(string substring)
        {
            var node = Navigate(root, 0, substring.Length, substring, text, false);
            if (!node.isFound)
            {
                yield break;
            }
 
            var stack = new Stack<Node>();
            if (node.childIndex < 0)
            {
                stack.Push(node.parent);
            }
            else
            {
                stack.Push(node.parent.children[node.childIndex]);
            }
 
            while (stack.Count > 0)
            {
                var current = stack.Pop();
 
                if (HasChildren(current))
                {
                    foreach (var child in current.children)
                    {
                        stack.Push(child);
                    }
                }
                else
                {
                    yield return current.pos;
                }
            }
        }
        #endregion
 
        #region Methods
        private static Location Navigate(Node parent, int from, int to, string substring, string text, bool useSkipCount)
        {
            var node = parent;
 
            if (from == to)
            {
                return new Location(true, node, from, 0, -1);
            }
 
            // Navigate to the end of substring
            var k = from;
            while (true)
            {
                var childIndex = FindChild(substring[k], node, text);
                if (childIndex < 0)
                {
                    return new Location(false, node, k, 0, -1);
                }
 
                var child = node.children[childIndex];
                var m = 0;
 
                if (useSkipCount)
                {
                    var skip = Math.Min(to - k, end(child, to + 1) - child.start);
                    m += skip;
                    k += skip;
                }
                else
                {
                    while (child.start + m < end(child, to + 1) &&
                           k < to &&
                           text[child.start + m] == substring[k])
                    {
                        ++m;
                        ++k;
                    }
                }
 
                if (k == to)
                {
                    return new Location(true, node, k, m, childIndex);
                }
                else if (child.start + m == end(child, to + 1))
                {
                    if (!HasChildren(child))
                    {
                        return new Location(false, node, k, m, childIndex);
                    }
                    node = child;
                }
                else
                {
                    return new Location(false, node, k, m, childIndex);
                }
            }
        }
 
        private static int end(Node node, int pos)
        {
            if (node.end == currentPosition)
                return pos - 1;
 
            return node.end;
        }
 
        private static int FindChild(char c, Node node, string text)
        {
            if (node.children == null)
            {
                return -1;
            }
 
            for (int i = 0; i < node.children.Count; ++i)
            {
                var child = node.children[i];
                if (text[child.start] == c)
                {
                    return i;
                }
            }
 
            return -1;
        }
 
        private static bool HasChildren(Node node)
        {
            return node.children != null;
        }
        #endregion
 
        #region Construction
        private Node Build(string text)
        {
            var builder = new UkkonenBuilder(text);
            return builder.Build();
        }
 
        private class UkkonenBuilder
        {
            private readonly string text;
            private readonly Node root;
 
            private Node activeLeaf;
            private Node nodeThatRequireSuffixLink;
 
            public UkkonenBuilder(string text)
            {
                this.text = text;
                this.root = new Node
                {
                    children = new List<Node>()
                };
            }
 
            public Node Build()
            {
                activeLeaf = ConstructT(0);
                var next = new Next(root, 1, 1, 0);
 
                for (int i = 1; i < text.Length; ++i)
                {
                    nodeThatRequireSuffixLink = null;
 
                    // Phase i+1
 
                    // So the first extension of any phase is special and only takes constant time since the algorithm
                    // has a pointer to the end of the current full string
                    // I.e. when j = 0
                    ApplyRule1(activeLeaf, i + 1);
 
                    while (next.j < i)
                    {
                        var location = Navigate(next.node, next.from, i, text, text, true);
                        next = ApplyRule(location, next.j, i);
 
                        if (next.rule == 3)
                        {
                            // Rule 3 stops current phase
                            break;
                        }
                    }
 
                    // Do not put TerminationCharacter to the tree
                    if (i < text.Length - 1)
                    {
                        // Extend empty suffix, by putting the next character to the tree
                        ConstructT(i);
                    }
                }
 
                foreach (var node in Visit(root))
                {
                    if (node.end == currentPosition)
                    {
                        node.end = text.Length;
                    }
                }
 
                return root;
            }
 
            private struct Next
            {
                public Node node;
                public int j;
                public int from;
                public int rule;
 
                public Next(Node node, int j, int from, int rule)
                {
                    this.node = node;
                    this.j = j;
                    this.from = from;
                    this.rule = rule;
                }
            }
 
            private Next ApplyRule(Location location, int j, int i)
            {
                if (location.childIndex == -1)
                {
                    ApplyRule2(location.parent, -1, location.offsetInEdge, location.offsetInString, j);
 
                    if (location.parent.suffixLink == null)
                    {
                        return new Next(root, j + 1, j + 1, 2);
                    }
                    else
                    {
                        return new Next(location.parent.suffixLink, j + 1, i, 2);
                    }
                }
 
                if (location.offsetInString != i)
                {
                    throw new Exception("What?");
                }
 
                var child = location.parent.children[location.childIndex];
                if (child.start + location.offsetInEdge == end(child, i + 1))
                {
                    if (HasChildren(child))
                    {
                        if (FindChild(child.children, text[i]) >= 0)
                        {
                            ApplyRule3();
 
                            return new Next(location.parent,
                                        j,
                                        i - location.offsetInEdge,
                                        3);
                        }
                        else
                        {
                            ApplyRule2(child, -1, 0, location.offsetInString, j);
 
                            if (child.suffixLink != null)
                            {
                                return new Next(child.suffixLink.parent,
                                                j + 1,
                                                i - (end(child.suffixLink, i + 1) - child.suffixLink.start),
                                                2);
                            }
                            else if (location.parent.suffixLink == null)
                            {
                                return new Next(root, j + 1, j + 1, 2);
                            }
                            else
                            {
                                return new Next(location.parent.suffixLink,
                                            j + 1,
                                            i - (end(child, i + 1) - child.start),
                                            2);
                            }
                        }
                    }
                    else
                    {
                        ApplyRule1(child, i + 1);
 
                        if (location.parent.suffixLink == null)
                        {
                            return new Next(root, j + 1, j + 1, 1);
                        }
                        else
                        {
                            return new Next(location.parent.suffixLink,
                                        j + 1,
                                        i - location.offsetInEdge,
                                        1);
                        }
                    }
                }
                else
                {
                    if (text[child.start + location.offsetInEdge] == text[i])
                    {
                        ApplyRule3();
 
                        return new Next(location.parent,
                                        j,
                                        i - location.offsetInEdge,
                                        3);
                    }
                    else
                    {
                        ApplyRule2(location.parent, location.childIndex, location.offsetInEdge, location.offsetInString, j);
 
                        if (location.parent.suffixLink == null)
                        {
                            if (location.parent.parent != null && location.parent.parent.suffixLink != null)
                            {
                                return new Next(location.parent.parent.suffixLink,
                                                j + 1,
                                                i - location.offsetInEdge - (end(location.parent, i + 1) - location.parent.start),
                                                2);
                            }
                            else
                            {
                                return new Next(root, j + 1, j + 1, 2);
                            }
                        }
                        else
                        {
                            return new Next(location.parent.suffixLink,
                                        j + 1,
                                        i - location.offsetInEdge,
                                        2);
                        }
                    }
                }
            }
 
            private Node ConstructT(int t)
            {
                var childIndex = FindChild(root.children, text[t]);
                if (childIndex >= 0)
                {
                    return root.children[childIndex];
                }
 
                var newNode = new Node
                {
                    start = t,
                    end = currentPosition,
                    pos = t,
                    parent = root
                };
 
                root.children.Add(newNode);
                return newNode;
            }
 
            private int FindChild(IList<Node> children, char c)
            {
                for (int i = 0; i < children.Count; ++i)
                {
                    if (text[children[i].start] == c)
                    {
                        return i;
                    }
                }
                return -1;
            }
 
            private void ApplyRule1(Node leaf, int newEnd)
            {
                //Rule 1. Path ends at a leaf. Extend implicitly
            }
 
            private void ApplyRule2(Node parent, int childIndex, int m, int k, int pos)
            {
                var newParent = default(Node);
                if (childIndex >= 0)
                {
                    //Rule 2. Split label and add new leaf
                    var child = parent.children[childIndex];
 
                    // 1) replace child with internal node
                    newParent = new Node
                    {
                        start = child.start,
                        end = child.start + m,
                        parent = parent,
 
                        suffixLink = null,
                        children = new List<Node>()
                    };
 
                    parent.children[childIndex] = newParent;
 
                    // 2) adjust start position of the child and add it to the new internal node as a child
                    child.start += m;
                    child.parent = newParent;
                    newParent.children.Add(child);
 
                    // Assign suffix link
                    {
                        // Corollary 6.1.1. In Ukkonen’s algorithm, any newly created internal node will have a
                        // suffix link from it by the end of the next extension.
                        //
                        // I.e. if an edge is split, which means a new node was created, and if that was not the first
                        // node created during the current phase, then connect the previously inserted node and the new node
                        // through a suffix link.
                        if (nodeThatRequireSuffixLink != null)
                        {
                            if (nodeThatRequireSuffixLink.suffixLink != null)
                            {
                                throw new Exception("What?");
                            }
                            nodeThatRequireSuffixLink.suffixLink = newParent;
                        }
                        nodeThatRequireSuffixLink = newParent;
                    }
                }
                else
                {
                    newParent = parent;
                }
 
                // 3) add the rest of the suffix as a new child
                if (newParent.children == null)
                {
                    newParent.children = new List<Node>();
                }
 
                newParent.children.Add(new Node
                {
                    start = k,
                    end = currentPosition,
                    parent = newParent,
 
                    pos = pos
                });
            }
 
            private void ApplyRule3()
            {
                //Rule 3. Suffix is already in the tree
                // Do nothing
            }
        }
        #endregion
 
        #region Visualization
 
        public override string ToDotNotation()
        {
            var dotText = new StringBuilder();
            dotText.AppendLine("digraph g {");
            dotText.AppendLine("node[shape = circle];");
 
            var labels = new Dictionary<Node, int>();
 
            // Nodes
            foreach (var node in Visit(root))
            {
                int index = GetLabelIndex(labels, node);
 
                if (!HasChildren(node))
                {
                    dotText.AppendLine($"node{index} [label=\"{node.pos}\"]");
                }
                else
                {
                    dotText.AppendLine($"node{index} [label=\"\"]");
 
                    foreach (var child in node.children.OrderBy(c => text[c.start]))
                    {
                        int childIndex = GetLabelIndex(labels, child);
                        dotText.AppendLine($"node{index} -> node{childIndex} [label=\"{text.Substring(child.start, end(child, text.Length + 1) - child.start)}\"]");
                    }
                }
 
                if (node.suffixLink != null && node.suffixLink != root)
                {
                    int suffixIndex = GetLabelIndex(labels, node.suffixLink);
                    dotText.AppendLine($"node{index} -> node{suffixIndex} [style=\"dashed\", constraint=false, color=silver]");
                }
            }
 
            dotText.AppendLine("}");
            return dotText.ToString();
        }
 
        private static int GetLabelIndex(Dictionary<Node, int> labels, Node node)
        {
        	int index;
            if (!labels.TryGetValue(node, out index))
            {
                index = labels.Count + 1;
                labels.Add(node, index);
            }
 
            return index;
        }
 
        private static IEnumerable<Node> Visit(Node root)
        {
            var stack = new Stack<Node>();
            stack.Push(root);
 
            while (stack.Count > 0)
            {
                var current = stack.Pop();
 
                if (HasChildren(current))
                {
                    foreach (var child in current.children)
                    {
                        stack.Push(child);
                    }
                }
 
                yield return current;
            }
        }
 
        #endregion
 
        #region Types
        class Node
        {
            public int start;
            public int end;
            public Node parent;
 
            // Leaf
            public int pos;
 
            // Internal
            public Node suffixLink;
            public IList<Node> children;
        }
 
        struct Location
        {
            public bool isFound;
            public Node parent;
            public int offsetInString;
            public int offsetInEdge;
            public int childIndex;
 
            public Location(bool isFound, Node parent, int offsetInString, int offsetInEdge, int childIndex)
            {
                this.isFound = isFound;
                this.parent = parent;
                this.offsetInString = offsetInString;
                this.offsetInEdge = offsetInEdge;
                this.childIndex = childIndex;
            }
        }
        #endregion
    }
 
	public class Test
	{
		public static void Main()
		{
            		var tree = SuffixTree.Build(Console.ReadLine(), SuffixTreeAlgorithm.UkkonenLinear);
            		Console.WriteLine("Use http://w...content-available-to-author-only...z.com to render the tree:");
            		Console.WriteLine(tree.ToDotNotation());
		}
	}
}

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uTGlucTsKdXNpbmcgU3lzdGVtLkNvbGxlY3Rpb25zLkdlbmVyaWM7CnVzaW5nIFN5c3RlbS5UZXh0OwoKbmFtZXNwYWNlIFBNUy5Db21tb24uQ29sbGVjdGlvbnMKewogICAgLy8gQWJzdHJhY3QgU3VmZml4IFRyZWUgY2xhc3MuIERlZmluZXMgaW50ZXJmYWNlIGZvciBkaWZmZXJlbnQgaW1wbGVtZW50YXRpb25zIG9mCiAgICAvLyBzdWZmaXggdHJlZSBjb25zdHJ1Y3Rpb24gYWxnb3JpdGhtcyBhbmQgaW50ZXJuYWwgcmVwcmVzZW50YXRpb25zCiAgICAvLwogICAgLy8gVXNhZ2UgZXhhbXBsZToKICAgIC8vICAgICAgICB2YXIgdHJlZSA9IFN1ZmZpeFRyZWUuQnVpbGQoImNhY2FvIiwgU3VmZml4VHJlZUFsZ29yaXRobS5Va2tvbmVuTGluZWFyKTsKICAgIC8vICAgICAgICB2YXIgbWF0Y2hlcyA9IHRyZWUuTWF0Y2goImNhIikuVG9BcnJheSgpOwogICAgLy8gICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKHRyZWUuVG9Eb3ROb3RhdGlvbigpKTsKICAgIC8vCiAgICAvLyBEb3Qgbm90YXRpb24gY2FuIGJlIHJlbmRlcmVkIGhlcmU6IGh0dHA6Ly93Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi56LmNvbQogICAgcHVibGljIGFic3RyYWN0IGNsYXNzIFN1ZmZpeFRyZWUKICAgIHsKICAgICAgICAjcmVnaW9uIEZpZWxkcwogICAgICAgIHByb3RlY3RlZCBzdGF0aWMgY2hhciBUZXJtaW5hdGlvbkNoYXJhY3RlciA9ICckJzsKICAgICAgICAjZW5kcmVnaW9uCgogICAgICAgICNyZWdpb24gQXBpCiAgICAgICAgcHVibGljIGFic3RyYWN0IGJvb2wgSXNNYXRjaChzdHJpbmcgc3Vic3RyaW5nKTsKCiAgICAgICAgcHVibGljIGFic3RyYWN0IElFbnVtZXJhYmxlPGludD4gTWF0Y2goc3RyaW5nIHN1YnN0cmluZyk7CgogICAgICAgIHB1YmxpYyBhYnN0cmFjdCBzdHJpbmcgVG9Eb3ROb3RhdGlvbigpOwogICAgICAgICNlbmRyZWdpb24KCiAgICAgICAgI3JlZ2lvbiBDb25zdHJ1Y3Rpb24KICAgICAgICBwdWJsaWMgc3RhdGljIFN1ZmZpeFRyZWUgQnVpbGQoc3RyaW5nIHRleHQsIFN1ZmZpeFRyZWVBbGdvcml0aG0gYWxnb3JpdGhtKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKHRleHQgPT0gIG51bGwpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHRocm93IG5ldyBBcmd1bWVudE51bGxFeGNlcHRpb24obmFtZW9mKHRleHQpKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgaWYgKHRleHQuQ29udGFpbnMoVGVybWluYXRpb25DaGFyYWN0ZXIpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB0aHJvdyBuZXcgQXJndW1lbnRFeGNlcHRpb24oIklucHV0IGNvbnRhaW5zIHRlcm1pbmF0aW9uIGNoYXJhY3RlciIsIG5hbWVvZih0ZXh0KSk7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHN3aXRjaCAoYWxnb3JpdGhtKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjYXNlIFN1ZmZpeFRyZWVBbGdvcml0aG0uVWtrb25lbkxpbmVhcjogLy8gTyhuKQogICAgICAgICAgICAgICAgICAgIHJldHVybiBuZXcgU3VmZml4VHJlZVVra29uZW5MaW5lYXIodGV4dCk7CgogICAgICAgICAgICAgICAgZGVmYXVsdDoKICAgICAgICAgICAgICAgICAgICB0aHJvdyBuZXcgTm90SW1wbGVtZW50ZWRFeGNlcHRpb24oJCJObyBpbXBsZW1lbnRhdGlvbiBmb3IgYWxnb3JpdG0ge2FsZ29yaXRobX0iKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAjZW5kcmVnaW9uCiAgICB9CgogICAgcHVibGljIGVudW0gU3VmZml4VHJlZUFsZ29yaXRobQogICAgewogICAgICAgIE5haXZlVXNpbmdUcmllLAogICAgICAgIE5haXZlLAogICAgICAgIFVra29uZW5DdWJpYywKICAgICAgICBVa2tvbmVuUXVhZHJhdGljLAogICAgICAgIFVra29uZW5MaW5lYXIsCiAgICAgICAgVWtrb25lbkZhc3QsCiAgICAgICAgV2VpbmVyLAogICAgICAgIE1jQ3JlaWdodAogICAgfQoJCiAgICAvLy8gPHN1bW1hcnk+CiAgICAvLy8gVWtrb25lbiBsaW5lYXIgdGltZSBPKG4pIGFsZ29yaXRobQogICAgLy8vIEFzIGRlc2NyaWJlZCBpbiB0aGUgYm9vayBieSBELiBHdXNmaWVsZCwgQWxnb3JpdGhtcyBvbiBTdHJpbmdzLCBUcmVlcyBhbmQgU2VxdWVuY2VzCiAgICAvLy8gPC9zdW1tYXJ5PgogICAgcHVibGljIGNsYXNzIFN1ZmZpeFRyZWVVa2tvbmVuTGluZWFyIDogU3VmZml4VHJlZQogICAgewogICAgICAgICNyZWdpb24gRmllbGRzCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgcmVhZG9ubHkgaW50IGN1cnJlbnRQb3NpdGlvbiA9IGludC5NaW5WYWx1ZTsKCiAgICAgICAgcHJpdmF0ZSByZWFkb25seSBOb2RlIHJvb3Q7CiAgICAgICAgcHJpdmF0ZSByZWFkb25seSBzdHJpbmcgdGV4dDsKICAgICAgICAjZW5kcmVnaW9uCgogICAgICAgICNyZWdpb24gQ29uc3RydWN0b3IKICAgICAgICBwdWJsaWMgU3VmZml4VHJlZVVra29uZW5MaW5lYXIoc3RyaW5nIGlucHV0VGV4dCkKICAgICAgICB7CiAgICAgICAgICAgIHRleHQgPSBpbnB1dFRleHQgKyBUZXJtaW5hdGlvbkNoYXJhY3RlcjsKICAgICAgICAgICAgcm9vdCA9IEJ1aWxkKHRleHQpOwogICAgICAgIH0KICAgICAgICAjZW5kcmVnaW9uCgogICAgICAgICNyZWdpb24gQXBpCiAgICAgICAgcHVibGljIG92ZXJyaWRlIGJvb2wgSXNNYXRjaChzdHJpbmcgc3Vic3RyaW5nKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIE1hdGNoKHN1YnN0cmluZykuQW55KCk7CiAgICAgICAgfQoKICAgICAgICBwdWJsaWMgb3ZlcnJpZGUgSUVudW1lcmFibGU8aW50PiBNYXRjaChzdHJpbmcgc3Vic3RyaW5nKQogICAgICAgIHsKICAgICAgICAgICAgdmFyIG5vZGUgPSBOYXZpZ2F0ZShyb290LCAwLCBzdWJzdHJpbmcuTGVuZ3RoLCBzdWJzdHJpbmcsIHRleHQsIGZhbHNlKTsKICAgICAgICAgICAgaWYgKCFub2RlLmlzRm91bmQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHlpZWxkIGJyZWFrOwogICAgICAgICAgICB9CgogICAgICAgICAgICB2YXIgc3RhY2sgPSBuZXcgU3RhY2s8Tm9kZT4oKTsKICAgICAgICAgICAgaWYgKG5vZGUuY2hpbGRJbmRleCA8IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHN0YWNrLlB1c2gobm9kZS5wYXJlbnQpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgc3RhY2suUHVzaChub2RlLnBhcmVudC5jaGlsZHJlbltub2RlLmNoaWxkSW5kZXhdKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgd2hpbGUgKHN0YWNrLkNvdW50ID4gMCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdmFyIGN1cnJlbnQgPSBzdGFjay5Qb3AoKTsKCiAgICAgICAgICAgICAgICBpZiAoSGFzQ2hpbGRyZW4oY3VycmVudCkpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgZm9yZWFjaCAodmFyIGNoaWxkIGluIGN1cnJlbnQuY2hpbGRyZW4pCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBzdGFjay5QdXNoKGNoaWxkKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgeWllbGQgcmV0dXJuIGN1cnJlbnQucG9zOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgICNlbmRyZWdpb24KCiAgICAgICAgI3JlZ2lvbiBNZXRob2RzCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgTG9jYXRpb24gTmF2aWdhdGUoTm9kZSBwYXJlbnQsIGludCBmcm9tLCBpbnQgdG8sIHN0cmluZyBzdWJzdHJpbmcsIHN0cmluZyB0ZXh0LCBib29sIHVzZVNraXBDb3VudCkKICAgICAgICB7CiAgICAgICAgICAgIHZhciBub2RlID0gcGFyZW50OwoKICAgICAgICAgICAgaWYgKGZyb20gPT0gdG8pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJldHVybiBuZXcgTG9jYXRpb24odHJ1ZSwgbm9kZSwgZnJvbSwgMCwgLTEpOwogICAgICAgICAgICB9CgogICAgICAgICAgICAvLyBOYXZpZ2F0ZSB0byB0aGUgZW5kIG9mIHN1YnN0cmluZwogICAgICAgICAgICB2YXIgayA9IGZyb207CiAgICAgICAgICAgIHdoaWxlICh0cnVlKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB2YXIgY2hpbGRJbmRleCA9IEZpbmRDaGlsZChzdWJzdHJpbmdba10sIG5vZGUsIHRleHQpOwogICAgICAgICAgICAgICAgaWYgKGNoaWxkSW5kZXggPCAwKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHJldHVybiBuZXcgTG9jYXRpb24oZmFsc2UsIG5vZGUsIGssIDAsIC0xKTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICB2YXIgY2hpbGQgPSBub2RlLmNoaWxkcmVuW2NoaWxkSW5kZXhdOwogICAgICAgICAgICAgICAgdmFyIG0gPSAwOwoKICAgICAgICAgICAgICAgIGlmICh1c2VTa2lwQ291bnQpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgdmFyIHNraXAgPSBNYXRoLk1pbih0byAtIGssIGVuZChjaGlsZCwgdG8gKyAxKSAtIGNoaWxkLnN0YXJ0KTsKICAgICAgICAgICAgICAgICAgICBtICs9IHNraXA7CiAgICAgICAgICAgICAgICAgICAgayArPSBza2lwOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHdoaWxlIChjaGlsZC5zdGFydCArIG0gPCBlbmQoY2hpbGQsIHRvICsgMSkgJiYKICAgICAgICAgICAgICAgICAgICAgICAgICAgayA8IHRvICYmCiAgICAgICAgICAgICAgICAgICAgICAgICAgIHRleHRbY2hpbGQuc3RhcnQgKyBtXSA9PSBzdWJzdHJpbmdba10pCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICArK207CiAgICAgICAgICAgICAgICAgICAgICAgICsrazsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgaWYgKGsgPT0gdG8pCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG5ldyBMb2NhdGlvbih0cnVlLCBub2RlLCBrLCBtLCBjaGlsZEluZGV4KTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UgaWYgKGNoaWxkLnN0YXJ0ICsgbSA9PSBlbmQoY2hpbGQsIHRvICsgMSkpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYgKCFIYXNDaGlsZHJlbihjaGlsZCkpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gbmV3IExvY2F0aW9uKGZhbHNlLCBub2RlLCBrLCBtLCBjaGlsZEluZGV4KTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgbm9kZSA9IGNoaWxkOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHJldHVybiBuZXcgTG9jYXRpb24oZmFsc2UsIG5vZGUsIGssIG0sIGNoaWxkSW5kZXgpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBwcml2YXRlIHN0YXRpYyBpbnQgZW5kKE5vZGUgbm9kZSwgaW50IHBvcykKICAgICAgICB7CiAgICAgICAgICAgIGlmIChub2RlLmVuZCA9PSBjdXJyZW50UG9zaXRpb24pCiAgICAgICAgICAgICAgICByZXR1cm4gcG9zIC0gMTsKCiAgICAgICAgICAgIHJldHVybiBub2RlLmVuZDsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIGludCBGaW5kQ2hpbGQoY2hhciBjLCBOb2RlIG5vZGUsIHN0cmluZyB0ZXh0KQogICAgICAgIHsKICAgICAgICAgICAgaWYgKG5vZGUuY2hpbGRyZW4gPT0gbnVsbCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcmV0dXJuIC0xOwogICAgICAgICAgICB9CgogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG5vZGUuY2hpbGRyZW4uQ291bnQ7ICsraSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdmFyIGNoaWxkID0gbm9kZS5jaGlsZHJlbltpXTsKICAgICAgICAgICAgICAgIGlmICh0ZXh0W2NoaWxkLnN0YXJ0XSA9PSBjKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHJldHVybiBpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CgogICAgICAgICAgICByZXR1cm4gLTE7CiAgICAgICAgfQoKICAgICAgICBwcml2YXRlIHN0YXRpYyBib29sIEhhc0NoaWxkcmVuKE5vZGUgbm9kZSkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiBub2RlLmNoaWxkcmVuICE9IG51bGw7CiAgICAgICAgfQogICAgICAgICNlbmRyZWdpb24KCiAgICAgICAgI3JlZ2lvbiBDb25zdHJ1Y3Rpb24KICAgICAgICBwcml2YXRlIE5vZGUgQnVpbGQoc3RyaW5nIHRleHQpCiAgICAgICAgewogICAgICAgICAgICB2YXIgYnVpbGRlciA9IG5ldyBVa2tvbmVuQnVpbGRlcih0ZXh0KTsKICAgICAgICAgICAgcmV0dXJuIGJ1aWxkZXIuQnVpbGQoKTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgY2xhc3MgVWtrb25lbkJ1aWxkZXIKICAgICAgICB7CiAgICAgICAgICAgIHByaXZhdGUgcmVhZG9ubHkgc3RyaW5nIHRleHQ7CiAgICAgICAgICAgIHByaXZhdGUgcmVhZG9ubHkgTm9kZSByb290OwoKICAgICAgICAgICAgcHJpdmF0ZSBOb2RlIGFjdGl2ZUxlYWY7CiAgICAgICAgICAgIHByaXZhdGUgTm9kZSBub2RlVGhhdFJlcXVpcmVTdWZmaXhMaW5rOwoKICAgICAgICAgICAgcHVibGljIFVra29uZW5CdWlsZGVyKHN0cmluZyB0ZXh0KQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB0aGlzLnRleHQgPSB0ZXh0OwogICAgICAgICAgICAgICAgdGhpcy5yb290ID0gbmV3IE5vZGUKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBjaGlsZHJlbiA9IG5ldyBMaXN0PE5vZGU+KCkKICAgICAgICAgICAgICAgIH07CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHB1YmxpYyBOb2RlIEJ1aWxkKCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgYWN0aXZlTGVhZiA9IENvbnN0cnVjdFQoMCk7CiAgICAgICAgICAgICAgICB2YXIgbmV4dCA9IG5ldyBOZXh0KHJvb3QsIDEsIDEsIDApOwoKICAgICAgICAgICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDwgdGV4dC5MZW5ndGg7ICsraSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBub2RlVGhhdFJlcXVpcmVTdWZmaXhMaW5rID0gbnVsbDsKCiAgICAgICAgICAgICAgICAgICAgLy8gUGhhc2UgaSsxCgogICAgICAgICAgICAgICAgICAgIC8vIFNvIHRoZSBmaXJzdCBleHRlbnNpb24gb2YgYW55IHBoYXNlIGlzIHNwZWNpYWwgYW5kIG9ubHkgdGFrZXMgY29uc3RhbnQgdGltZSBzaW5jZSB0aGUgYWxnb3JpdGhtCiAgICAgICAgICAgICAgICAgICAgLy8gaGFzIGEgcG9pbnRlciB0byB0aGUgZW5kIG9mIHRoZSBjdXJyZW50IGZ1bGwgc3RyaW5nCiAgICAgICAgICAgICAgICAgICAgLy8gSS5lLiB3aGVuIGogPSAwCiAgICAgICAgICAgICAgICAgICAgQXBwbHlSdWxlMShhY3RpdmVMZWFmLCBpICsgMSk7CgogICAgICAgICAgICAgICAgICAgIHdoaWxlIChuZXh0LmogPCBpKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgdmFyIGxvY2F0aW9uID0gTmF2aWdhdGUobmV4dC5ub2RlLCBuZXh0LmZyb20sIGksIHRleHQsIHRleHQsIHRydWUpOwogICAgICAgICAgICAgICAgICAgICAgICBuZXh0ID0gQXBwbHlSdWxlKGxvY2F0aW9uLCBuZXh0LmosIGkpOwoKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKG5leHQucnVsZSA9PSAzKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLyBSdWxlIDMgc3RvcHMgY3VycmVudCBwaGFzZQogICAgICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgICAgIC8vIERvIG5vdCBwdXQgVGVybWluYXRpb25DaGFyYWN0ZXIgdG8gdGhlIHRyZWUKICAgICAgICAgICAgICAgICAgICBpZiAoaSA8IHRleHQuTGVuZ3RoIC0gMSkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIC8vIEV4dGVuZCBlbXB0eSBzdWZmaXgsIGJ5IHB1dHRpbmcgdGhlIG5leHQgY2hhcmFjdGVyIHRvIHRoZSB0cmVlCiAgICAgICAgICAgICAgICAgICAgICAgIENvbnN0cnVjdFQoaSk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIGZvcmVhY2ggKHZhciBub2RlIGluIFZpc2l0KHJvb3QpKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmIChub2RlLmVuZCA9PSBjdXJyZW50UG9zaXRpb24pCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBub2RlLmVuZCA9IHRleHQuTGVuZ3RoOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICByZXR1cm4gcm9vdDsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcHJpdmF0ZSBzdHJ1Y3QgTmV4dAogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBwdWJsaWMgTm9kZSBub2RlOwogICAgICAgICAgICAgICAgcHVibGljIGludCBqOwogICAgICAgICAgICAgICAgcHVibGljIGludCBmcm9tOwogICAgICAgICAgICAgICAgcHVibGljIGludCBydWxlOwoKICAgICAgICAgICAgICAgIHB1YmxpYyBOZXh0KE5vZGUgbm9kZSwgaW50IGosIGludCBmcm9tLCBpbnQgcnVsZSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICB0aGlzLm5vZGUgPSBub2RlOwogICAgICAgICAgICAgICAgICAgIHRoaXMuaiA9IGo7CiAgICAgICAgICAgICAgICAgICAgdGhpcy5mcm9tID0gZnJvbTsKICAgICAgICAgICAgICAgICAgICB0aGlzLnJ1bGUgPSBydWxlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CgogICAgICAgICAgICBwcml2YXRlIE5leHQgQXBwbHlSdWxlKExvY2F0aW9uIGxvY2F0aW9uLCBpbnQgaiwgaW50IGkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChsb2NhdGlvbi5jaGlsZEluZGV4ID09IC0xKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIEFwcGx5UnVsZTIobG9jYXRpb24ucGFyZW50LCAtMSwgbG9jYXRpb24ub2Zmc2V0SW5FZGdlLCBsb2NhdGlvbi5vZmZzZXRJblN0cmluZywgaik7CgogICAgICAgICAgICAgICAgICAgIGlmIChsb2NhdGlvbi5wYXJlbnQuc3VmZml4TGluayA9PSBudWxsKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG5ldyBOZXh0KHJvb3QsIGogKyAxLCBqICsgMSwgMik7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBuZXcgTmV4dChsb2NhdGlvbi5wYXJlbnQuc3VmZml4TGluaywgaiArIDEsIGksIDIpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBpZiAobG9jYXRpb24ub2Zmc2V0SW5TdHJpbmcgIT0gaSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICB0aHJvdyBuZXcgRXhjZXB0aW9uKCJXaGF0PyIpOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIHZhciBjaGlsZCA9IGxvY2F0aW9uLnBhcmVudC5jaGlsZHJlbltsb2NhdGlvbi5jaGlsZEluZGV4XTsKICAgICAgICAgICAgICAgIGlmIChjaGlsZC5zdGFydCArIGxvY2F0aW9uLm9mZnNldEluRWRnZSA9PSBlbmQoY2hpbGQsIGkgKyAxKSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpZiAoSGFzQ2hpbGRyZW4oY2hpbGQpKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKEZpbmRDaGlsZChjaGlsZC5jaGlsZHJlbiwgdGV4dFtpXSkgPj0gMCkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgQXBwbHlSdWxlMygpOwoKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBuZXcgTmV4dChsb2NhdGlvbi5wYXJlbnQsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBqLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaSAtIGxvY2F0aW9uLm9mZnNldEluRWRnZSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDMpOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgQXBwbHlSdWxlMihjaGlsZCwgLTEsIDAsIGxvY2F0aW9uLm9mZnNldEluU3RyaW5nLCBqKTsKCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiAoY2hpbGQuc3VmZml4TGluayAhPSBudWxsKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBuZXcgTmV4dChjaGlsZC5zdWZmaXhMaW5rLnBhcmVudCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaiArIDEsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGkgLSAoZW5kKGNoaWxkLnN1ZmZpeExpbmssIGkgKyAxKSAtIGNoaWxkLnN1ZmZpeExpbmsuc3RhcnQpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAyKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UgaWYgKGxvY2F0aW9uLnBhcmVudC5zdWZmaXhMaW5rID09IG51bGwpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG5ldyBOZXh0KHJvb3QsIGogKyAxLCBqICsgMSwgMik7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG5ldyBOZXh0KGxvY2F0aW9uLnBhcmVudC5zdWZmaXhMaW5rLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGogKyAxLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGkgLSAoZW5kKGNoaWxkLCBpICsgMSkgLSBjaGlsZC5zdGFydCksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMik7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgQXBwbHlSdWxlMShjaGlsZCwgaSArIDEpOwoKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGxvY2F0aW9uLnBhcmVudC5zdWZmaXhMaW5rID09IG51bGwpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBuZXcgTmV4dChyb290LCBqICsgMSwgaiArIDEsIDEpOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG5ldyBOZXh0KGxvY2F0aW9uLnBhcmVudC5zdWZmaXhMaW5rLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaiArIDEsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpIC0gbG9jYXRpb24ub2Zmc2V0SW5FZGdlLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMSk7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYgKHRleHRbY2hpbGQuc3RhcnQgKyBsb2NhdGlvbi5vZmZzZXRJbkVkZ2VdID09IHRleHRbaV0pCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBBcHBseVJ1bGUzKCk7CgogICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gbmV3IE5leHQobG9jYXRpb24ucGFyZW50LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGkgLSBsb2NhdGlvbi5vZmZzZXRJbkVkZ2UsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAzKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgQXBwbHlSdWxlMihsb2NhdGlvbi5wYXJlbnQsIGxvY2F0aW9uLmNoaWxkSW5kZXgsIGxvY2F0aW9uLm9mZnNldEluRWRnZSwgbG9jYXRpb24ub2Zmc2V0SW5TdHJpbmcsIGopOwoKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGxvY2F0aW9uLnBhcmVudC5zdWZmaXhMaW5rID09IG51bGwpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChsb2NhdGlvbi5wYXJlbnQucGFyZW50ICE9IG51bGwgJiYgbG9jYXRpb24ucGFyZW50LnBhcmVudC5zdWZmaXhMaW5rICE9IG51bGwpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG5ldyBOZXh0KGxvY2F0aW9uLnBhcmVudC5wYXJlbnQuc3VmZml4TGluaywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaiArIDEsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGkgLSBsb2NhdGlvbi5vZmZzZXRJbkVkZ2UgLSAoZW5kKGxvY2F0aW9uLnBhcmVudCwgaSArIDEpIC0gbG9jYXRpb24ucGFyZW50LnN0YXJ0KSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMik7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG5ldyBOZXh0KHJvb3QsIGogKyAxLCBqICsgMSwgMik7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gbmV3IE5leHQobG9jYXRpb24ucGFyZW50LnN1ZmZpeExpbmssCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBqICsgMSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGkgLSBsb2NhdGlvbi5vZmZzZXRJbkVkZ2UsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAyKTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQoKICAgICAgICAgICAgcHJpdmF0ZSBOb2RlIENvbnN0cnVjdFQoaW50IHQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHZhciBjaGlsZEluZGV4ID0gRmluZENoaWxkKHJvb3QuY2hpbGRyZW4sIHRleHRbdF0pOwogICAgICAgICAgICAgICAgaWYgKGNoaWxkSW5kZXggPj0gMCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICByZXR1cm4gcm9vdC5jaGlsZHJlbltjaGlsZEluZGV4XTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICB2YXIgbmV3Tm9kZSA9IG5ldyBOb2RlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgc3RhcnQgPSB0LAogICAgICAgICAgICAgICAgICAgIGVuZCA9IGN1cnJlbnRQb3NpdGlvbiwKICAgICAgICAgICAgICAgICAgICBwb3MgPSB0LAogICAgICAgICAgICAgICAgICAgIHBhcmVudCA9IHJvb3QKICAgICAgICAgICAgICAgIH07CgogICAgICAgICAgICAgICAgcm9vdC5jaGlsZHJlbi5BZGQobmV3Tm9kZSk7CiAgICAgICAgICAgICAgICByZXR1cm4gbmV3Tm9kZTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcHJpdmF0ZSBpbnQgRmluZENoaWxkKElMaXN0PE5vZGU+IGNoaWxkcmVuLCBjaGFyIGMpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgY2hpbGRyZW4uQ291bnQ7ICsraSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpZiAodGV4dFtjaGlsZHJlbltpXS5zdGFydF0gPT0gYykKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIHJldHVybiAtMTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcHJpdmF0ZSB2b2lkIEFwcGx5UnVsZTEoTm9kZSBsZWFmLCBpbnQgbmV3RW5kKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvL1J1bGUgMS4gUGF0aCBlbmRzIGF0IGEgbGVhZi4gRXh0ZW5kIGltcGxpY2l0bHkKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcHJpdmF0ZSB2b2lkIEFwcGx5UnVsZTIoTm9kZSBwYXJlbnQsIGludCBjaGlsZEluZGV4LCBpbnQgbSwgaW50IGssIGludCBwb3MpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHZhciBuZXdQYXJlbnQgPSBkZWZhdWx0KE5vZGUpOwogICAgICAgICAgICAgICAgaWYgKGNoaWxkSW5kZXggPj0gMCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAvL1J1bGUgMi4gU3BsaXQgbGFiZWwgYW5kIGFkZCBuZXcgbGVhZgogICAgICAgICAgICAgICAgICAgIHZhciBjaGlsZCA9IHBhcmVudC5jaGlsZHJlbltjaGlsZEluZGV4XTsKCiAgICAgICAgICAgICAgICAgICAgLy8gMSkgcmVwbGFjZSBjaGlsZCB3aXRoIGludGVybmFsIG5vZGUKICAgICAgICAgICAgICAgICAgICBuZXdQYXJlbnQgPSBuZXcgTm9kZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgc3RhcnQgPSBjaGlsZC5zdGFydCwKICAgICAgICAgICAgICAgICAgICAgICAgZW5kID0gY2hpbGQuc3RhcnQgKyBtLAogICAgICAgICAgICAgICAgICAgICAgICBwYXJlbnQgPSBwYXJlbnQsCgogICAgICAgICAgICAgICAgICAgICAgICBzdWZmaXhMaW5rID0gbnVsbCwKICAgICAgICAgICAgICAgICAgICAgICAgY2hpbGRyZW4gPSBuZXcgTGlzdDxOb2RlPigpCiAgICAgICAgICAgICAgICAgICAgfTsKCiAgICAgICAgICAgICAgICAgICAgcGFyZW50LmNoaWxkcmVuW2NoaWxkSW5kZXhdID0gbmV3UGFyZW50OwoKICAgICAgICAgICAgICAgICAgICAvLyAyKSBhZGp1c3Qgc3RhcnQgcG9zaXRpb24gb2YgdGhlIGNoaWxkIGFuZCBhZGQgaXQgdG8gdGhlIG5ldyBpbnRlcm5hbCBub2RlIGFzIGEgY2hpbGQKICAgICAgICAgICAgICAgICAgICBjaGlsZC5zdGFydCArPSBtOwogICAgICAgICAgICAgICAgICAgIGNoaWxkLnBhcmVudCA9IG5ld1BhcmVudDsKICAgICAgICAgICAgICAgICAgICBuZXdQYXJlbnQuY2hpbGRyZW4uQWRkKGNoaWxkKTsKCiAgICAgICAgICAgICAgICAgICAgLy8gQXNzaWduIHN1ZmZpeCBsaW5rCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAvLyBDb3JvbGxhcnkgNi4xLjEuIEluIFVra29uZW7igJlzIGFsZ29yaXRobSwgYW55IG5ld2x5IGNyZWF0ZWQgaW50ZXJuYWwgbm9kZSB3aWxsIGhhdmUgYQogICAgICAgICAgICAgICAgICAgICAgICAvLyBzdWZmaXggbGluayBmcm9tIGl0IGJ5IHRoZSBlbmQgb2YgdGhlIG5leHQgZXh0ZW5zaW9uLgogICAgICAgICAgICAgICAgICAgICAgICAvLwogICAgICAgICAgICAgICAgICAgICAgICAvLyBJLmUuIGlmIGFuIGVkZ2UgaXMgc3BsaXQsIHdoaWNoIG1lYW5zIGEgbmV3IG5vZGUgd2FzIGNyZWF0ZWQsIGFuZCBpZiB0aGF0IHdhcyBub3QgdGhlIGZpcnN0CiAgICAgICAgICAgICAgICAgICAgICAgIC8vIG5vZGUgY3JlYXRlZCBkdXJpbmcgdGhlIGN1cnJlbnQgcGhhc2UsIHRoZW4gY29ubmVjdCB0aGUgcHJldmlvdXNseSBpbnNlcnRlZCBub2RlIGFuZCB0aGUgbmV3IG5vZGUKICAgICAgICAgICAgICAgICAgICAgICAgLy8gdGhyb3VnaCBhIHN1ZmZpeCBsaW5rLgogICAgICAgICAgICAgICAgICAgICAgICBpZiAobm9kZVRoYXRSZXF1aXJlU3VmZml4TGluayAhPSBudWxsKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiAobm9kZVRoYXRSZXF1aXJlU3VmZml4TGluay5zdWZmaXhMaW5rICE9IG51bGwpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdGhyb3cgbmV3IEV4Y2VwdGlvbigiV2hhdD8iKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIG5vZGVUaGF0UmVxdWlyZVN1ZmZpeExpbmsuc3VmZml4TGluayA9IG5ld1BhcmVudDsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBub2RlVGhhdFJlcXVpcmVTdWZmaXhMaW5rID0gbmV3UGFyZW50OwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBuZXdQYXJlbnQgPSBwYXJlbnQ7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgLy8gMykgYWRkIHRoZSByZXN0IG9mIHRoZSBzdWZmaXggYXMgYSBuZXcgY2hpbGQKICAgICAgICAgICAgICAgIGlmIChuZXdQYXJlbnQuY2hpbGRyZW4gPT0gbnVsbCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBuZXdQYXJlbnQuY2hpbGRyZW4gPSBuZXcgTGlzdDxOb2RlPigpOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIG5ld1BhcmVudC5jaGlsZHJlbi5BZGQobmV3IE5vZGUKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBzdGFydCA9IGssCiAgICAgICAgICAgICAgICAgICAgZW5kID0gY3VycmVudFBvc2l0aW9uLAogICAgICAgICAgICAgICAgICAgIHBhcmVudCA9IG5ld1BhcmVudCwKCiAgICAgICAgICAgICAgICAgICAgcG9zID0gcG9zCiAgICAgICAgICAgICAgICB9KTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcHJpdmF0ZSB2b2lkIEFwcGx5UnVsZTMoKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvL1J1bGUgMy4gU3VmZml4IGlzIGFscmVhZHkgaW4gdGhlIHRyZWUKICAgICAgICAgICAgICAgIC8vIERvIG5vdGhpbmcKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAjZW5kcmVnaW9uCgogICAgICAgICNyZWdpb24gVmlzdWFsaXphdGlvbgoKICAgICAgICBwdWJsaWMgb3ZlcnJpZGUgc3RyaW5nIFRvRG90Tm90YXRpb24oKQogICAgICAgIHsKICAgICAgICAgICAgdmFyIGRvdFRleHQgPSBuZXcgU3RyaW5nQnVpbGRlcigpOwogICAgICAgICAgICBkb3RUZXh0LkFwcGVuZExpbmUoImRpZ3JhcGggZyB7Iik7CiAgICAgICAgICAgIGRvdFRleHQuQXBwZW5kTGluZSgibm9kZVtzaGFwZSA9IGNpcmNsZV07Iik7CgogICAgICAgICAgICB2YXIgbGFiZWxzID0gbmV3IERpY3Rpb25hcnk8Tm9kZSwgaW50PigpOwoKICAgICAgICAgICAgLy8gTm9kZXMKICAgICAgICAgICAgZm9yZWFjaCAodmFyIG5vZGUgaW4gVmlzaXQocm9vdCkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCBpbmRleCA9IEdldExhYmVsSW5kZXgobGFiZWxzLCBub2RlKTsKCiAgICAgICAgICAgICAgICBpZiAoIUhhc0NoaWxkcmVuKG5vZGUpKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGRvdFRleHQuQXBwZW5kTGluZSgkIm5vZGV7aW5kZXh9IFtsYWJlbD1cIntub2RlLnBvc31cIl0iKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBkb3RUZXh0LkFwcGVuZExpbmUoJCJub2Rle2luZGV4fSBbbGFiZWw9XCJcIl0iKTsKCiAgICAgICAgICAgICAgICAgICAgZm9yZWFjaCAodmFyIGNoaWxkIGluIG5vZGUuY2hpbGRyZW4uT3JkZXJCeShjID0+IHRleHRbYy5zdGFydF0pKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaW50IGNoaWxkSW5kZXggPSBHZXRMYWJlbEluZGV4KGxhYmVscywgY2hpbGQpOwogICAgICAgICAgICAgICAgICAgICAgICBkb3RUZXh0LkFwcGVuZExpbmUoJCJub2Rle2luZGV4fSAtPiBub2Rle2NoaWxkSW5kZXh9IFtsYWJlbD1cInt0ZXh0LlN1YnN0cmluZyhjaGlsZC5zdGFydCwgZW5kKGNoaWxkLCB0ZXh0Lkxlbmd0aCArIDEpIC0gY2hpbGQuc3RhcnQpfVwiXSIpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBpZiAobm9kZS5zdWZmaXhMaW5rICE9IG51bGwgJiYgbm9kZS5zdWZmaXhMaW5rICE9IHJvb3QpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaW50IHN1ZmZpeEluZGV4ID0gR2V0TGFiZWxJbmRleChsYWJlbHMsIG5vZGUuc3VmZml4TGluayk7CiAgICAgICAgICAgICAgICAgICAgZG90VGV4dC5BcHBlbmRMaW5lKCQibm9kZXtpbmRleH0gLT4gbm9kZXtzdWZmaXhJbmRleH0gW3N0eWxlPVwiZGFzaGVkXCIsIGNvbnN0cmFpbnQ9ZmFsc2UsIGNvbG9yPXNpbHZlcl0iKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQoKICAgICAgICAgICAgZG90VGV4dC5BcHBlbmRMaW5lKCJ9Iik7CiAgICAgICAgICAgIHJldHVybiBkb3RUZXh0LlRvU3RyaW5nKCk7CiAgICAgICAgfQoKICAgICAgICBwcml2YXRlIHN0YXRpYyBpbnQgR2V0TGFiZWxJbmRleChEaWN0aW9uYXJ5PE5vZGUsIGludD4gbGFiZWxzLCBOb2RlIG5vZGUpCiAgICAgICAgewogICAgICAgIAlpbnQgaW5kZXg7CiAgICAgICAgICAgIGlmICghbGFiZWxzLlRyeUdldFZhbHVlKG5vZGUsIG91dCBpbmRleCkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGluZGV4ID0gbGFiZWxzLkNvdW50ICsgMTsKICAgICAgICAgICAgICAgIGxhYmVscy5BZGQobm9kZSwgaW5kZXgpOwogICAgICAgICAgICB9CgogICAgICAgICAgICByZXR1cm4gaW5kZXg7CiAgICAgICAgfQoKICAgICAgICBwcml2YXRlIHN0YXRpYyBJRW51bWVyYWJsZTxOb2RlPiBWaXNpdChOb2RlIHJvb3QpCiAgICAgICAgewogICAgICAgICAgICB2YXIgc3RhY2sgPSBuZXcgU3RhY2s8Tm9kZT4oKTsKICAgICAgICAgICAgc3RhY2suUHVzaChyb290KTsKCiAgICAgICAgICAgIHdoaWxlIChzdGFjay5Db3VudCA+IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHZhciBjdXJyZW50ID0gc3RhY2suUG9wKCk7CgogICAgICAgICAgICAgICAgaWYgKEhhc0NoaWxkcmVuKGN1cnJlbnQpKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGZvcmVhY2ggKHZhciBjaGlsZCBpbiBjdXJyZW50LmNoaWxkcmVuKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgc3RhY2suUHVzaChjaGlsZCk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIHlpZWxkIHJldHVybiBjdXJyZW50OwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICAjZW5kcmVnaW9uCgogICAgICAgICNyZWdpb24gVHlwZXMKICAgICAgICBjbGFzcyBOb2RlCiAgICAgICAgewogICAgICAgICAgICBwdWJsaWMgaW50IHN0YXJ0OwogICAgICAgICAgICBwdWJsaWMgaW50IGVuZDsKICAgICAgICAgICAgcHVibGljIE5vZGUgcGFyZW50OwoKICAgICAgICAgICAgLy8gTGVhZgogICAgICAgICAgICBwdWJsaWMgaW50IHBvczsKCiAgICAgICAgICAgIC8vIEludGVybmFsCiAgICAgICAgICAgIHB1YmxpYyBOb2RlIHN1ZmZpeExpbms7CiAgICAgICAgICAgIHB1YmxpYyBJTGlzdDxOb2RlPiBjaGlsZHJlbjsKICAgICAgICB9CgogICAgICAgIHN0cnVjdCBMb2NhdGlvbgogICAgICAgIHsKICAgICAgICAgICAgcHVibGljIGJvb2wgaXNGb3VuZDsKICAgICAgICAgICAgcHVibGljIE5vZGUgcGFyZW50OwogICAgICAgICAgICBwdWJsaWMgaW50IG9mZnNldEluU3RyaW5nOwogICAgICAgICAgICBwdWJsaWMgaW50IG9mZnNldEluRWRnZTsKICAgICAgICAgICAgcHVibGljIGludCBjaGlsZEluZGV4OwoKICAgICAgICAgICAgcHVibGljIExvY2F0aW9uKGJvb2wgaXNGb3VuZCwgTm9kZSBwYXJlbnQsIGludCBvZmZzZXRJblN0cmluZywgaW50IG9mZnNldEluRWRnZSwgaW50IGNoaWxkSW5kZXgpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHRoaXMuaXNGb3VuZCA9IGlzRm91bmQ7CiAgICAgICAgICAgICAgICB0aGlzLnBhcmVudCA9IHBhcmVudDsKICAgICAgICAgICAgICAgIHRoaXMub2Zmc2V0SW5TdHJpbmcgPSBvZmZzZXRJblN0cmluZzsKICAgICAgICAgICAgICAgIHRoaXMub2Zmc2V0SW5FZGdlID0gb2Zmc2V0SW5FZGdlOwogICAgICAgICAgICAgICAgdGhpcy5jaGlsZEluZGV4ID0gY2hpbGRJbmRleDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAjZW5kcmVnaW9uCiAgICB9CgoJcHVibGljIGNsYXNzIFRlc3QKCXsKCQlwdWJsaWMgc3RhdGljIHZvaWQgTWFpbigpCgkJewogICAgICAgICAgICAJCXZhciB0cmVlID0gU3VmZml4VHJlZS5CdWlsZChDb25zb2xlLlJlYWRMaW5lKCksIFN1ZmZpeFRyZWVBbGdvcml0aG0uVWtrb25lbkxpbmVhcik7CiAgICAgICAgICAgIAkJQ29uc29sZS5Xcml0ZUxpbmUoIlVzZSBodHRwOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uei5jb20gdG8gcmVuZGVyIHRoZSB0cmVlOiIpOwogICAgICAgICAgICAJCUNvbnNvbGUuV3JpdGVMaW5lKHRyZWUuVG9Eb3ROb3RhdGlvbigpKTsKCQl9Cgl9Cn0=

Success #stdin #stdout 0.03s 17644KB

stdin

copy

cacao

stdout

copy

Use http://w...content-available-to-author-only...z.com to render the tree:
digraph g {
node[shape = circle];
node1 [label=""]
node1 -> node2 [label="a"]
node1 -> node3 [label="ca"]
node1 -> node4 [label="o$"]
node4 [label="4"]
node2 [label=""]
node2 -> node5 [label="cao$"]
node2 -> node6 [label="o$"]
node6 [label="3"]
node5 [label="1"]
node3 [label=""]
node3 -> node7 [label="cao$"]
node3 -> node8 [label="o$"]
node3 -> node2 [style="dashed", constraint=false, color=silver]
node8 [label="2"]
node7 [label="0"]
}

https://ideone.com/Brm8RR

Suffix tree construction using Ukkonen's linear time O(n) algorithm

language:

C# (gmcs 5.20.1)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language