Sunday算法思想跟BM算法很相似,在婚配失败时存眷的是文本串中参与婚配的最末位字符的下一位字符,下面小编为大师收拾整顿了c#实现sunday算法实例,但愿能帮到大师!
因正则表达式搜索总是呈现死循环,入手下手考虑改成其他搜索体式格局,因为.net自带的IndexOf默认只能找到第一个或最后一个,假如要把全部的婚配项都找出来,还必要本人写循环SubString,所以想找下有无现成的,就发明了在这个范畴里,BM算法是霸道,而sunday算法据说是今朝最好的改良版,这一点我没有从国外的网站尤其是wiki上找到印证,但中文评论辩论sunday的文章很多,我就姑且认为它是最好的`吧。
复制代码 代码如下:
public static int SundaySearchstring 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
ifm==text.Length-1break;
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.GetPositionFirstcontext, pattern, true;
//
//watch.Stop;
//Console.WriteLinewatch.ElapsedMilliseconds;
watch.Reset;
watch.Start;
for int i = 0; i < count; i++
int pos = context.IndexOfpattern;
watch.Stop;
Console.WriteLinewatch.ElapsedMilliseconds;
watch.Reset;
watch.Start;
for int i = 0; i < count; i++
int pos = Sunday.SundaySearchcontext, pattern;
watch.Stop;
Console.WriteLinewatch.ElapsedMilliseconds;
在可以找到婚配与不克不及找到婚配两种环境下,sunday算法耗时大约是indexof的20%摆布。算法的确有用。
但千万不要使用substring来实现算法,那样会新生成很多字符串中间变量,算法带来的好处远远不如分派内存复制字符串的耗费大,解释掉的局部就是使用substring实现的,比indexof慢很多。