C#，字符串匹配（模式搜索）RK（Rabin Karp）算法的源代码-Toy模板网

这篇具有很好参考价值的文章主要介绍了C#，字符串匹配（模式搜索）RK（Rabin Karp）算法的源代码。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

alpha_code_max,C#算法演义 Algorithm Recipes,c#,算法,字符串查找算法

M.O.Rabin

Rabin-Karp算法，是由M.O.Rabin和R.A.Karp设计实现的一种基于移动散列值的字符串匹配算法。

通常基于散列值的字符串匹配方法：（1）首先计算模式字符串的散列函数；（2）然后利用相同的散列函数计算文本中所有可能的M个字符的子字符串的散列函数值并寻找匹配。但是这种方法比暴力查找还慢，因为计算散列值会涉及字符串中的每个字符。Rabin和Karp对上述方法进行了改进，设计实现了一种能够在常数时间内算出M个字符的子字符串散列值的方法。

alpha_code_max,C#算法演义 Algorithm Recipes,c#,算法,字符串查找算法

运行效果：

alpha_code_max,C#算法演义 Algorithm Recipes,c#,算法,字符串查找算法

源代码：

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文章来源地址https://www.toymoban.com/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;
        }
    }
}

到了这里，关于C#，字符串匹配（模式搜索）RK（Rabin Karp）算法的源代码的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！