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慢很多。