c#實現sunday算法實例

Sunday算法思想跟BM算法很相似,在匹配失敗時關注的是文本串中參加匹配的最末位字符的下一位字符，下面小編為大家整理了c#實現sunday算法實例，希望能幫到大家！

因正則表達式搜索總是出現死循環，開始考慮改為其他搜索方式，因為自帶的IndexOf默認只能找到第一個或最後一個，如果要把全部的匹配項都找出來，還需要自己寫循環SubString，所以想找下有沒有現成的，就發現了在這個領域裏，BM算法是王道，而sunday算法據説是目前最好的改進版，這一點我沒有從國外的網站尤其是wiki上找到印證，但中文談論sunday的文章很多，我就姑且認為它是最好的`吧。

複製代碼 代碼如下:

public static int SundaySearch(string text, string pattern)

{

int i = 0;

int j = 0;

int m = th ;

int matchPosition = i;

while (i < th && j < th)

{

if (text[i] == pattern[j])

{

i++;

j++;

}

else

{

if(m==th-1)break;

int k = th - 1;

while (k >= 0 && text[m ] != pattern[k])

{

k--;

}

int gap = th - k;

i += gap;

m = i + th;

if (m > th) m = th - 1;

matchPosition = i;

j = 0;

}

}

if (i <= th)

{

return matchPosition;

}

return -1;

}

好了，現在測試下性能：

複製代碼 代碼如下:

public static void PerformanceTest()

{

StreamReader reader = new StreamReader("D:", I);

string context = ToEnd();

string pattern = "xxxx";

int count = 1000*10;

Stopwatch watch=new Stopwatch();

//t();

//for (int i = 0; i < count; i++)

//{

// int pos= ositionFirst(context, pattern, true);

//}

//();

//eLine(sedMilliseconds);

t();

t();

for (int i = 0; i < count; i++)

{

int pos = xOf(pattern);

}

();

eLine(sedMilliseconds);

t();

t();

for (int i = 0; i < count; i++)

{

int pos = aySearch(context, pattern);

}

();

eLine(sedMilliseconds);

}

在可以找到匹配與不能找到匹配兩種情況下，sunday算法耗時大概是indexof的20%左右。算法確實有用。

但千萬不要使用substring來實現算法，那樣會新生成很多字符串中間變量，算法帶來的好處遠遠不如分配內存複製字符串的消耗大，註釋掉的部分就是使用substring實現的，比indexof慢很多。