c#实现sunday算法实例

相关推荐

c#实现sunday算法实例

　　Sunday算法思想跟BM算法很相似,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符，下面小编为大家整理了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慢很多。

【c#实现sunday算法实例】相关文章：

C#数据结构之循环链表的实例代码10-22

PHP实现抽奖概率算法09-13

权重随机算法的java实现08-13

C#抽象工厂模式的几种实现方法及比较10-20