public class Trie
{
  private class Node
  {
    /// 

    /// 是否单词根节点
    /// 
    public bool isTail = false;

    public Dictionary nextNode;

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

  /// 

  /// 根节点
  /// 
  private Node rootNode;
  private int size;
  private int maxLength;

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

  /// 

  /// 字典树中存储的单词的最大长度
  /// 
  /// 
  public int MaxLength()
  {
    return maxLength;
  }

  /// 

  /// 字典树中存储的单词数量
  /// 
  public int Size()
  {
    return size;
  }

  /// 

  /// 获取字典树中所有的词
  /// 
  public List GetWordList()
  {
    return GetStrList(this.rootNode);
  }

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

    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 subWordList = GetStrList(childNode);
        foreach (string subWord in subWordList)
        {
          wordList.Add(firstWord + subWord);
        }
      }
    }

    return wordList;
  }

  /// 

  /// 向字典中添加新的单词
  /// 
  /// 
  public void Add(string word)
  {
    //从根节点开始
    Node cur = this.rootNode;
    //循环遍历单词
    foreach (char c in word.ToCharArray())
    {
      //如果字典树节点中没有这个字母，则添加
      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++;
  }

  /// 

  /// 查询字典中某单词是否存在
  /// 
  /// 
  /// 
  public bool Contains(string word)
  {
    return Match(rootNode, word);
  }

  /// 

  /// 查找匹配
  /// 
  /// 
  /// 
  /// 
  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 errorWords)
    {
      foreach (var errorWord in errorWords)
      {
        trie.Add(errorWord);
      }
    }

    /// 

    /// 最大 正向/逆向 匹配错词
    /// 
    /// 需要匹配错词的字符串
    /// true为从左到右分词，false为从右到左分词
    /// 匹配到的错词
    public List MatchErrorWord(string inputStr, bool leftToRight)
    {
      if (string.IsNullOrWhiteSpace(inputStr))
        return null;
      if (trie.Size() == 0)
      {
        throw new ArgumentException("字典树没有数据,请先调用 LoadTrieData 方法装载字典树");
      }
      //取词的最大长度
      int maxLength = trie.MaxLength();
      //取词的当前长度
      int wordLength = maxLength;
      //分词操作中，处于字符串中的当前位置
      int position = 0;
      //分词操作中，已经处理的字符串总长度
      int segLength = 0;
      //用于尝试分词的取词字符串
      string word = "";

      //用于储存正向分词的字符串数组
      List segWords = new List();
      //用于储存逆向分词的字符串数组
      List segWordsReverse = new List();

      //开始分词，循环以下操作，直到全部完成
      while (segLength < inputStr.Length)
      {
        //如果剩余没分词的字符串长度<取词的最大长度，则取词长度等于剩余未分词长度
        if ((inputStr.Length - segLength) < maxLength)
          wordLength = inputStr.Length - segLength;
        //否则，按最大长度处理
        else
          wordLength = maxLength;

        //从左到右 和 从右到左截取时，起始位置不同
        //刚开始，截取位置是字符串两头，随着不断循环分词，截取位置会不断推进
        if (leftToRight)
          position = segLength;
        else
          position = inputStr.Length - segLength - wordLength;

        //按照指定长度，从字符串截取一个词
        word = inputStr.Substring(position, wordLength);


        //在字典中查找，是否存在这样一个词
        //如果不包含，就减少一个字符，再次在字典中查找
        //如此循环，直到只剩下一个字为止
        while (!trie.Contains(word))
        {
          //如果最后一个字都没有匹配，则把word设置为空，用来表示没有匹配项(如果是分词直接break)
          if (word.Length == 1)
          {
            word = null;
            break;
          }

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

        //将分出匹配上的词，加入到分词字符串数组中，正向和逆向不同
        if (word != null)
        {
          if (leftToRight)
            segWords.Add(word);
          else
            segWordsReverse.Add(word);
          //已经完成分词的字符串长度，要相应增加
          segLength += word.Length;
        }
        else
        {
          //没匹配上的则+1，丢掉一个字（如果是分词 则不用判断word是否为空，单个字也返回）
          segLength += 1;
        }
      }

      //如果是逆向分词，对分词结果反转排序
      if (!leftToRight)
      {
        for (int i = segWordsReverse.Count - 1; i >= 0; i--)
        {
          //将反转的结果，保存在正向分词数组中 以便最后return 同一个变量segWords
          segWords.Add(segWordsReverse[i]);
        }
      }

      return segWords;
    }
  }