C#,字符串匹配(模式搜索)BF(Brute Force)暴力算法的源代码

发布时间:2024年01月16日

字符串匹配算法(模式搜索 Pattern Search)的应用于包括但不限于:生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测、论文查重等等等等。

一、字符串匹配算法(模式搜索)

字符串匹配算法,就是在一个字符串text中查找是否存在一个(或多个)模式字符串pattern。

如: "ABCDEFG" 中是否存在 “EF” ?有几个?

常见的字符串匹配算法:

1、BF(Brute Force,暴力算法);

2、RK (Robin-Karp 算法);

3、KMP (D.E.Knuth、J.H.Morris、V.R.Pratt 算法);

4、哈希Hash与移动哈希算法;

二、BF(Brute Force,暴力算法)

BF 算法是一种原始、低级的穷举算法。

简单,就是顺序逐个比较呗。

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

namespace Legalsoft.Truffer.Algorithm
{
	/// <summary>
	/// 字符串匹配(模式搜索)算法集锦
	/// </summary>
	public static partial class PatternSearch
	{
		/// <summary>
		/// 字符串匹配的暴力算法(1)
		/// </summary>
		/// <param name="text"></param>
		/// <param name="pattern"></param>
		/// <returns></returns>
		public static List<int> NativeSearch_Original(string text, string pattern)
		{
			int pt = pattern.Length;
			List<int> matchs = new List<int>();
			for (int i = 0; i < (text.Length - pt); i++)
			{
				if (text.Substring(i, pt) == pattern)
				{
					matchs.Add(i);
				}
			}
			return matchs;
		}

		/// <summary>
		/// 字符串匹配的暴力算法(2)
		/// </summary>
		/// <param name="text"></param>
		/// <param name="pattern"></param>
		/// <returns></returns>
		public static List<int> NativeSearch(string text, string pattern)
		{
			int M = pattern.Length;
			int N = text.Length;
			int S = N - M;

			List<int> matchs = new List<int>();
			if (S <= 0) return matchs;
			for (int i = 0; i <= S; i++)
			{
				int j = 0;
				while (j < M)
				{
					if (text[i + j] != pattern[j])
					{
						break;
					}
					j++;
				}

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

			return matchs;
		}
	}
}

文章来源:https://blog.csdn.net/beijinghorn/article/details/124068909
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。