簡介
Sunday演算法是一種字串匹配演算法，相比于KMP演算法，它比較簡單易學，
在有些時候，比如字串很長的時候，它是比KMP要高效的，
核心思想
-
從前往后匹配，匹配失敗時關注主串中參與匹配的最末位字符的下一位，
-
該字符沒有在模式串中出現，則直接跳過，且模式串移動位數 = 模式串長度 + 1，
-
否則，移動位數 = 模式串長度 - 該字符在模式串最右出現出現的位置，
這三步說明了具體的執行，感覺很抽象，但綜合起來就是：
- 匹配時從前向后匹配，
- 匹配失敗時，重新對齊模式串與主串，
所以現在的問題是，這個重新對齊是怎么對齊呢？
舉個栗子
- 設主串為 eurusdoveyesido
- 設模式為 esid
- 正常匹配，在第2位發現不匹配，于是看主串中參與匹配的最末位字符的下一位，也就是s，s也在模式串出現過，那么對齊
- 對齊后，繼續正常匹配，發現第1位就不同，匹配失敗，同樣，看v，發現v沒在模式串出現過，那么模式串就與v后面的e對齊
- 同樣，匹配失敗，對齊i
- 終于，匹配成功！
代碼實作
_next陣列
是的，Sunday演算法也有next陣列需要預處理，
next陣列存盤的是：模式串不同字符最右邊的下標，
所以，對于上面例子的模式串 esid
- \(next[d] = 3\)
- \(next[i] = 2\)
- \(next[s] = 1\)
- \(next[e] = 0\)
而對于英文字符，它們都在ASCII里，總計256個，所以我們開一個256大小的陣列
int _next[256];
void getnext(char pattern[])
{
int len = strlen(pattern);
int i;
for(i = 0;i < 256; i ++)//初始化為 -1
{
_next[i] = -1;
}
int cnt = 0;
for(i = len - 1;i >= 0;i --)
{
if(_next[i] == -1)
{
_next[(int)pattern[i]] = i;
cnt ++;
if(cnt == 256)//256滿了就退出
{
break;
}
}
}
}
這樣的預處理，正是以空間換取時間
匹配程序
匹配的代碼按思想寫就好，值得一提的是：
因為模式串中沒有出現的字符的next值為-1，所以正好，當要對齊的時候，模式串多向后移動了一位（減 負 1 -> 加 1），
int SundaySearch(char pattern[],char dest[])
{
getnext(pattern);
int i, j, k;
int lenp = strlen(pattern),lend = strlen(dest);
for(i = 0;i < lend;)
{
j = i;
for(k = 0;k < lenp && j < lend; k ++)//匹配的程序
{
if(dest[j] == pattern[k])
{
j ++;
}else
{
break;
}
}
if(k == lenp)//匹配成功，回傳首字符下標
{
return i;
}else
{
if(i + lenp < lend)//注意越界
{
i += lenp - _next[(int)dest[i + lenp]];
}
else
{
return -1;
}
}
}
return -1;
}
本文來自博客園，作者：江水為竭，轉載請注明原文鏈接：https://www.cnblogs.com/Az1r/p/16751593.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/510912.html
標籤：其他
上一篇：Petrozavodsk Winter Training Camp 2016: Moscow SU Trinity Contest
下一篇：黑蘋果外接顯示幕廉價方案