字符串匹配算法 – Sunday算法

假设我们有如下字符串：

A = "LESSONS TEARNED IN SOFTWARE TE";

B = "SOFTWARE";

Sunday算法的大致原理是：

先从左到右逐个字符比较，以我们的字符串为例：

开始的时候，我们让i = 0, 指向A的第一个字符; j = 0 指向B的第一个字符，分别为"L"和"S"，不等；这个时候，Sunday算法要求，找到位于A字串中位于B字符串后面的第一个字符，即下图中 m所指向的字符"T"，在模式字符串B中从后向前查找是否存在"T"，

可以看到下图中k指向的字符与m指向的字符相等，

这时就将相等的字符对齐，让j再次指向B字符串的头一个字符，相应地，将i指向主串对应的字符N

再次比较A[i]和B[j]，不等，这时再次寻找主串中在模式串后面的那个字符

我们看到，模式串的最后一个字符与m指向的主串字符相等，因此再次移动子串

这时，主串i对应的字符是S，j对应的子串字符也是S，i++, j++

现在再次不等，m指向字符"D"

….

直到找到，或者i到达主串的末尾

C#代码如下：

static int SundaySearch(string text, string pattern)

{

int i = 0;

int j = 0;

int pe = pattern.Length - 1;

int tb = i;

int te = text.Length - 1;

while (i < text.Length && j < pattern.Length)

{

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

{

i++;

j++;

}

else

{

int k = pattern.Length - 1;

while (k >= 0 && text[pe + 1] != pattern[k])

{

k--;

}

int gap = pattern.Length - k;

i += gap;

pe = i + pattern.Length - 1;

tb = i;

j = 0;

}

if (i <= text.Length)

{

return tb;

}

return -1;

}