public class Trie
{
  private class Node
  {
    /// <summary>
    /// 是否單詞根節(jié)點
    /// </summary>
    public bool isTail = false;

    public Dictionary<char, Node> nextNode;

    public Node(bool isTail)
    {
      this.isTail = isTail;
      this.nextNode = new Dictionary<char, Node>();
    }
    public Node() : this(false)
    {
    }
  }

  /// <summary>
  /// 根節(jié)點
  /// </summary>
  private Node rootNode;
  private int size;
  private int maxLength;

  public Trie()
  {
    this.rootNode = new Node();
    this.size = 0;
    this.maxLength = 0;
  }

  /// <summary>
  /// 字典樹中存儲的單詞的最大長度
  /// </summary>
  /// <returns></returns>
  public int MaxLength()
  {
    return maxLength;
  }

  /// <summary>
  /// 字典樹中存儲的單詞數(shù)量
  /// </summary>
  public int Size()
  {
    return size;
  }

  /// <summary>
  /// 獲取字典樹中所有的詞
  /// </summary>
  public List<string> GetWordList()
  {
    return GetStrList(this.rootNode);
  }

  private List<string> GetStrList(Node node)
  {
    List<string> wordList = new List<string>();

    foreach (char nextChar in node.nextNode.Keys)
    {
      string firstWord = Convert.ToString(nextChar);
      Node childNode = node.nextNode[nextChar];

      if (childNode == null || childNode.nextNode.Count == 0)
      {
        wordList.Add(firstWord);
      }
      else
      {

        if (childNode.isTail)
        {
          wordList.Add(firstWord);
        }

        List<string> subWordList = GetStrList(childNode);
        foreach (string subWord in subWordList)
        {
          wordList.Add(firstWord + subWord);
        }
      }
    }

    return wordList;
  }

  /// <summary>
  /// 向字典中添加新的單詞
  /// </summary>
  /// <param name="word"></param>
  public void Add(string word)
  {
    //從根節(jié)點開始
    Node cur = this.rootNode;
    //循環(huán)遍歷單詞
    foreach (char c in word.ToCharArray())
    {
      //如果字典樹節(jié)點中沒有這個字母，則添加
      if (!cur.nextNode.ContainsKey(c))
      {
        cur.nextNode.Add(c, new Node());
      }
      cur = cur.nextNode[c];
    }
    cur.isTail = true;

    if (word.Length > this.maxLength)
    {
      this.maxLength = word.Length;
    }
    size++;
  }

  /// <summary>
  /// 查詢字典中某單詞是否存在
  /// </summary>
  /// <param name="word"></param>
  /// <returns></returns>
  public bool Contains(string word)
  {
    return Match(rootNode, word);
  }

  /// <summary>
  /// 查找匹配
  /// </summary>
  /// <param name="node"></param>
  /// <param name="word"></param>
  /// <returns></returns>
  private bool Match(Node node, string word)
  {
    if (word.Length == 0)
    {
      if (node.isTail)
      {
        return true;
      }
      else
      {
        return false;
      }
    }
    else
    {
      char firstChar = word.ElementAt(0);
      if (!node.nextNode.ContainsKey(firstChar))
      {
        return false;
      }
      else
      {
        Node childNode = node.nextNode[firstChar];
        return Match(childNode, word.Substring(1, word.Length - 1));
      }
    }
  }
}

public class ErrorWordMatch
  {
    private static ErrorWordMatch singleton = new ErrorWordMatch();
    private static Trie trie = new Trie();
    private ErrorWordMatch()
    {

    }

    public static ErrorWordMatch Singleton()
    {
      return singleton;
    }

    public void LoadTrieData(List<string> errorWords)
    {
      foreach (var errorWord in errorWords)
      {
        trie.Add(errorWord);
      }
    }

    /// <summary>
    /// 最大 正向/逆向 匹配錯詞
    /// </summary>
    /// <param name="inputStr">需要匹配錯詞的字符串</param>
    /// <param name="leftToRight">true為從左到右分詞，false為從右到左分詞</param>
    /// <returns>匹配到的錯詞</returns>
    public List<string> MatchErrorWord(string inputStr, bool leftToRight)
    {
      if (string.IsNullOrWhiteSpace(inputStr))
        return null;
      if (trie.Size() == 0)
      {
        throw new ArgumentException("字典樹沒有數(shù)據(jù),請先調(diào)用 LoadTrieData 方法裝載字典樹");
      }
      //取詞的最大長度
      int maxLength = trie.MaxLength();
      //取詞的當前長度
      int wordLength = maxLength;
      //分詞操作中，處于字符串中的當前位置
      int position = 0;
      //分詞操作中，已經(jīng)處理的字符串總長度
      int segLength = 0;
      //用于嘗試分詞的取詞字符串
      string word = "";

      //用于儲存正向分詞的字符串數(shù)組
      List<string> segWords = new List<string>();
      //用于儲存逆向分詞的字符串數(shù)組
      List<string> segWordsReverse = new List<string>();

      //開始分詞，循環(huán)以下操作，直到全部完成
      while (segLength < inputStr.Length)
      {
        //如果剩余沒分詞的字符串長度<取詞的最大長度，則取詞長度等于剩余未分詞長度
        if ((inputStr.Length - segLength) < maxLength)
          wordLength = inputStr.Length - segLength;
        //否則，按最大長度處理
        else
          wordLength = maxLength;

        //從左到右 和 從右到左截取時，起始位置不同
        //剛開始，截取位置是字符串兩頭，隨著不斷循環(huán)分詞，截取位置會不斷推進
        if (leftToRight)
          position = segLength;
        else
          position = inputStr.Length - segLength - wordLength;

        //按照指定長度，從字符串截取一個詞
        word = inputStr.Substring(position, wordLength);


        //在字典中查找，是否存在這樣一個詞
        //如果不包含，就減少一個字符，再次在字典中查找
        //如此循環(huán)，直到只剩下一個字為止
        while (!trie.Contains(word))
        {
          //如果最后一個字都沒有匹配，則把word設(shè)置為空，用來表示沒有匹配項(如果是分詞直接break)
          if (word.Length == 1)
          {
            word = null;
            break;
          }

          //把截取的字符串，最邊上的一個字去掉
          //從左到右 和 從右到左時，截掉的字符的位置不同
          if (leftToRight)
            word = word.Substring(0, word.Length - 1);
          else
            word = word.Substring(1);
        }

        //將分出匹配上的詞，加入到分詞字符串數(shù)組中，正向和逆向不同
        if (word != null)
        {
          if (leftToRight)
            segWords.Add(word);
          else
            segWordsReverse.Add(word);
          //已經(jīng)完成分詞的字符串長度，要相應(yīng)增加
          segLength += word.Length;
        }
        else
        {
          //沒匹配上的則+1，丟掉一個字（如果是分詞 則不用判斷word是否為空，單個字也返回）
          segLength += 1;
        }
      }

      //如果是逆向分詞，對分詞結(jié)果反轉(zhuǎn)排序
      if (!leftToRight)
      {
        for (int i = segWordsReverse.Count - 1; i >= 0; i--)
        {
          //將反轉(zhuǎn)的結(jié)果，保存在正向分詞數(shù)組中 以便最后return 同一個變量segWords
          segWords.Add(segWordsReverse[i]);
        }
      }

      return segWords;
    }
  }