?M.O.Rabin

Rabin-Karp算法，是由M.O.Rabin和R.A.Karp設(shè)計(jì)實(shí)現(xiàn)的一種基于移動(dòng)散列值的字符串匹配算法。

通常基于散列值的字符串匹配方法：（1）首先計(jì)算模式字符串的散列函數(shù)；（2）然后利用相同的散列函數(shù)計(jì)算文本中所有可能的M個(gè)字符的子字符串的散列函數(shù)值并尋找匹配。但是這種方法比暴力查找還慢，因?yàn)橛?jì)算散列值會(huì)涉及字符串中的每個(gè)字符。Rabin和Karp對(duì)上述方法進(jìn)行了改進(jìn)，設(shè)計(jì)實(shí)現(xiàn)了一種能夠在常數(shù)時(shí)間內(nèi)算出M個(gè)字符的子字符串散列值的方法。

運(yùn)行效果：

源代碼：

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

namespace Legalsoft.Truffer.Algorithm
{
?? ?public static partial class PatternSearch
?? ?{
?? ??? ?public readonly static int ALPHA_CODE_MAX = 256;

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

?? ??? ??? ?int M = pattern.Length;
?? ??? ??? ?int N = text.Length;

?? ??? ??? ?int h = 1;
?? ??? ??? ?for (int i = 0; i < M - 1; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?h = (h * ALPHA_CODE_MAX) % primeNumber;
?? ??? ??? ?}

?? ??? ??? ?int p = 0;
?? ??? ??? ?int t = 0;
?? ??? ??? ?for (int i = 0; i < M; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?p = (ALPHA_CODE_MAX * p + pattern[i]) % primeNumber;
?? ??? ??? ??? ?t = (ALPHA_CODE_MAX * t + text[i]) % primeNumber;
?? ??? ??? ?}

?? ??? ??? ?for (int i = 0; i <= N - M; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?if (p == t)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?int j;
?? ??? ??? ??? ??? ?for (j = 0; j < M; j++)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?if (text[i + j] != pattern[j])
?? ??? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?}

?? ??? ??? ??? ??? ?if (j == M)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?matchs.Add(i);
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}

?? ??? ??? ??? ?if (i < (N - M))
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?t = (ALPHA_CODE_MAX * (t - text[i] * h) + text[i + M]) % primeNumber;
?? ??? ??? ??? ??? ?if (t < 0)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?t = (t + primeNumber);
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ?}

?? ??? ??? ?return matchs;
?? ??? ?}
?? ?}
}
?

----------------------------------------------------------------

POWER BY TRUFFER.CN文章來源地址http://www.zghlxwxcb.cn/news/detail-803868.html

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

namespace Legalsoft.Truffer.Algorithm
{
?? ?public static partial class PatternSearch
?? ?{
?? ??? ?public readonly static int ALPHA_CODE_MAX = 256;

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

?? ??? ??? ?int M = pattern.Length;
?? ??? ??? ?int N = text.Length;

?? ??? ??? ?int h = 1;
?? ??? ??? ?for (int i = 0; i < M - 1; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?h = (h * ALPHA_CODE_MAX) % primeNumber;
?? ??? ??? ?}

?? ??? ??? ?int p = 0;
?? ??? ??? ?int t = 0;
?? ??? ??? ?for (int i = 0; i < M; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?p = (ALPHA_CODE_MAX * p + pattern[i]) % primeNumber;
?? ??? ??? ??? ?t = (ALPHA_CODE_MAX * t + text[i]) % primeNumber;
?? ??? ??? ?}

?? ??? ??? ?for (int i = 0; i <= N - M; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?if (p == t)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?int j;
?? ??? ??? ??? ??? ?for (j = 0; j < M; j++)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?if (text[i + j] != pattern[j])
?? ??? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?}

?? ??? ??? ??? ??? ?if (j == M)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?matchs.Add(i);
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}

?? ??? ??? ??? ?if (i < (N - M))
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?t = (ALPHA_CODE_MAX * (t - text[i] * h) + text[i + M]) % primeNumber;
?? ??? ??? ??? ??? ?if (t < 0)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?t = (t + primeNumber);
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ?}

?? ??? ??? ?return matchs;
?? ??? ?}
?? ?}
}

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