xingd.net

原文見http://www.rzrgm.cn/goody9807/archive/2006/09/12/502094.html，很多網站都轉載了。

但在我這里測試的時候，RegEx要快一倍左右。但是還是不太滿意，因為我們網站上臟字過濾用的相當多，對效率已經有了一些影響，經過一番思考后，自己做了一個算法。在自己的機器上測試了一下，使用原文中的臟字庫，0x19c的字符串長度，1000次循環，文本查找耗時1933.47ms，RegEx用了1216.719ms，而我的算法只用了244.125ms.

更新：新增一個BitArray，用于判斷某char是否在所有臟字中出現過。總時間由244ms降到了34ms.

主要算法如代碼所示

      private static Dictionary dic = new Dictionary();
      private static BitArray fastcheck = new BitArray(char.MaxValue);

      static void Prepare()
      {
          string[] badwords =  // read from file
           foreach (string word in badwords)
            {
                if (!dic.ContainsKey(word))
                {
                    dic.Add(word, null);
                    maxlength = Math.Max(maxlength, word.Length);
                    fastcheck[word[0]] = true;
                }
            }
      }

使用的時候

int index = 0;

while (index < target.Length)

{

    if (!fastcheck[target[index]])

    {

        while (index < target.Length - 1 && !fastcheck[target[++index]]) ;

    }



    for (int j = 0; j < Math.Min(maxlength, target.Length - index); j++)

    {

        string sub = target.Substring(index, j);

        if (dic.ContainsKey(sub))

        {

            sb.Replace(sub, "***", index, j);

            index += j;

            break;

        }

    }



    index++;

}