Sunday算法是Daniel M.Sunday于1990年提出的一種字符串模式匹配算法。

核心思想：在匹配過程中，模式串并不被要求一定要按從左向右進(jìn)行比較還是從右向左進(jìn)行比較，它在發(fā)現(xiàn)不匹配時，算法能跳過盡可能多的字符以進(jìn)行下一步的匹配，從而提高了匹配效率。

Sunday算法思想跟BM（Boyer Moore）算法很相似，在匹配失敗時關(guān)注的是文本串中參加匹配的最末位字符的下一位字符。如果該字符沒有在匹配串中出現(xiàn)則直接跳過，即：移動步長=匹配串長度+1；否則，同BM算法一樣，其移動步長=匹配串中最右端的該字符到末尾的距離+1。
?

本代碼運(yùn)行效果：

源代碼：

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
?? ?public static partial class PatternSearch
?? ?{
?? ??? ?/// <summary>
?? ??? ?/// 字符位置表
?? ??? ?/// </summary>
?? ??? ?private static int ALPHA_BET = 512;

?? ??? ?/// <summary>
?? ??? ?/// 計(jì)算字符的出現(xiàn)位置表
?? ??? ?/// </summary>
?? ??? ?/// <param name="pattern"></param>
?? ??? ?/// <returns></returns>
?? ??? ?private static int[] ComputeOccurence(string pattern)
?? ??? ?{
?? ??? ??? ?int[] table = new int[ALPHA_BET];
?? ??? ??? ?for (char a = (char)0; a < (char)ALPHA_BET; a++)
?? ??? ??? ?{
?? ??? ??? ??? ?table[(int)a] = -1;
?? ??? ??? ?}

?? ??? ??? ?for (int i = 0; i < pattern.Length; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?char a = pattern[i];
?? ??? ??? ??? ?table[(int)a] = i;
?? ??? ??? ?}
?? ??? ??? ?return table;
?? ??? ?}

?? ??? ?/// <summary>
?? ??? ?/// 字符串匹配算法（模式搜索）Sunday算法
?? ??? ?/// </summary>
?? ??? ?/// <param name="text"></param>
?? ??? ?/// <param name="pattern"></param>
?? ??? ?/// <returns></returns>
?? ??? ?public static List<int> Sunday_Search(string text, string pattern)
?? ??? ?{
?? ??? ??? ?List<int> matchs = new List<int>();

?? ??? ??? ?int i = 0;
?? ??? ??? ?int[] table = ComputeOccurence(pattern);
?? ??? ??? ?while (i <= text.Length - pattern.Length)
?? ??? ??? ?{
?? ??? ??? ??? ?int j = 0;
?? ??? ??? ??? ?while (j < pattern.Length && text[i + j] == pattern[j])
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?j++;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?if (j == pattern.Length)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?matchs.Add(i);
?? ??? ??? ??? ?}
?? ??? ??? ??? ?i += pattern.Length;
?? ??? ??? ??? ?if (i < text.Length)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?i -= table[(int)text[i]];
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?return matchs;
?? ??? ?}
?? ?}
}

?——————————————————————

POWER BY 315SOFT.COM &
TRUFFER.CN文章來源地址http://www.zghlxwxcb.cn/news/detail-819288.html

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
?? ?public static partial class PatternSearch
?? ?{
?? ??? ?/// <summary>
?? ??? ?/// 字符位置表
?? ??? ?/// </summary>
?? ??? ?private static int ALPHA_BET = 512;

?? ??? ?/// <summary>
?? ??? ?/// 計(jì)算字符的出現(xiàn)位置表
?? ??? ?/// </summary>
?? ??? ?/// <param name="pattern"></param>
?? ??? ?/// <returns></returns>
?? ??? ?private static int[] ComputeOccurence(string pattern)
?? ??? ?{
?? ??? ??? ?int[] table = new int[ALPHA_BET];
?? ??? ??? ?for (char a = (char)0; a < (char)ALPHA_BET; a++)
?? ??? ??? ?{
?? ??? ??? ??? ?table[(int)a] = -1;
?? ??? ??? ?}

?? ??? ??? ?for (int i = 0; i < pattern.Length; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?char a = pattern[i];
?? ??? ??? ??? ?table[(int)a] = i;
?? ??? ??? ?}
?? ??? ??? ?return table;
?? ??? ?}

?? ??? ?/// <summary>
?? ??? ?/// 字符串匹配算法（模式搜索）Sunday算法
?? ??? ?/// </summary>
?? ??? ?/// <param name="text"></param>
?? ??? ?/// <param name="pattern"></param>
?? ??? ?/// <returns></returns>
?? ??? ?public static List<int> Sunday_Search(string text, string pattern)
?? ??? ?{
?? ??? ??? ?List<int> matchs = new List<int>();

?? ??? ??? ?int i = 0;
?? ??? ??? ?int[] table = ComputeOccurence(pattern);
?? ??? ??? ?while (i <= text.Length - pattern.Length)
?? ??? ??? ?{
?? ??? ??? ??? ?int j = 0;
?? ??? ??? ??? ?while (j < pattern.Length && text[i + j] == pattern[j])
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?j++;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?if (j == pattern.Length)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?matchs.Add(i);
?? ??? ??? ??? ?}
?? ??? ??? ??? ?i += pattern.Length;
?? ??? ??? ??? ?if (i < text.Length)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?i -= table[(int)text[i]];
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?return matchs;
?? ??? ?}
?? ?}
}

到了這里，關(guān)于C#，字符串匹配（模式搜索）Sunday算法的源代碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！