Алгоритмы на строках

План:

  • Алгоритм Кнута-Морриса-Пратта
  • Алгоритм Ахо-Корасик
        static TreeNode ConstructTrie(List<string> dictionary)
        {
            TreeNode root = new TreeNode(-1);
            for (int n = 0; n < dictionary.Count; n++)
            {
                TreeNode ptr = root;
                TreeNode trans = null;
                string s = dictionary[n];
                for (int i = 0; i < s.Length; i++)
                {
                    string symbol = s[i].ToString();
                    if (trans == null)
                    {
                        if (ptr.Nodes.ContainsKey(symbol))
                        {
                            trans = ptr.Nodes[symbol];
                        }
                        else
                        {
                            if (i == (s.Length - 1))
                            {
                                ptr.Add(n, symbol);
                            }
                            else
                            {
                                ptr.Add(-1, symbol);
                                trans = ptr.Nodes[symbol];
                            }
                        }
                    }
                    else
                    {
                        if (trans.Nodes.ContainsKey(symbol))
                        {
                            trans = trans.Nodes[symbol];
                        }
                        else
                        {
                            if (i == (s.Length - 1))
                            {
                                trans.Add(n, symbol);
                            }
                            else
                            {
                                trans.Add(-1, symbol);
                                trans = trans.Nodes[symbol];
                            }
                        }
                    }
                }
                root = ptr;
            }

            return root;
        }
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License