c#实现sunday算法实例

因正则表达式搜索总是出现死循环，开始考虑改为其他搜索方式，因为.net自带的indexof默认只能找到第一个或最后一个，如果要把全部的匹配项都找出来，还需要自己写循环substring，所以想找下有没有现成的，就发现了在这个领域里，bm算法是王道，而sunday算法据说是目前最好的改进版，这一点我没有从国外的网站尤其是wiki上找到印证，但中文谈论sunday的文章很多，我就姑且认为它是最好的吧。

public static int sundaysearch(string text, string pattern)
        {
            int i = 0;
            int j = 0;
            int m = pattern.length ;

            int matchposition = i;

            while (i < text.length && j < pattern.length)
            {
                if (text[i] == pattern[j])
                {
                    i++;
                    j++;
                }
                else
                {
                    if(m==text.length-1)break;

                    int k = pattern.length - 1;

                    while (k >= 0 && text[m ] != pattern[k])
                    {
                        k--;
                    }

                    int gap = pattern.length - k;
                    i += gap;
                    m = i + pattern.length;
                    if (m > text.length) m = text.length - 1;
                    matchposition = i;
                    j = 0;
                }
            }

            if (i <= text.length)
            {
                return matchposition;
            }

            return -1;
        }

好了，现在测试下性能：

public static void performancetest()
        {
            streamreader reader = new streamreader("d:\\logconfiguration.xml", encoding.ascii);
            string context = reader.readtoend();
            string pattern = "xxxx";
            int count = 1000*10;

            stopwatch watch=new stopwatch();

            //watch.start();
            //for (int i = 0; i < count; i++)
            //{
            //    int pos= sunday.getpositionfirst(context, pattern, true);
            //}
            //watch.stop();
            //console.writeline(watch.elapsedmilliseconds);

            watch.reset();
            watch.start();
            for (int i = 0; i < count; i++)
            {
                int pos = context.indexof(pattern);
            }
            watch.stop();
            console.writeline(watch.elapsedmilliseconds);

            watch.reset();
            watch.start();
            for (int i = 0; i < count; i++)
            {
                int pos = sunday.sundaysearch(context, pattern);
            }
            watch.stop();
            console.writeline(watch.elapsedmilliseconds);
        }

在可以找到匹配与不能找到匹配两种情况下，sunday算法耗时大概是indexof的20%左右。算法确实有用。

但千万不要使用substring来实现算法，那样会新生成很多字符串中间变量，算法带来的好处远远不如分配内存复制字符串的消耗大，注释掉的部分就是使用substring实现的，比indexof慢很多。