顾剑辉 (solarsoft)
引言
任何有效的应用程序都要处理文本信息，诸如编辑、排版、信息检索、文档分析、知识发掘、语意识别等，这些均需用到文本串的提取和定位。在很多程序设计语言中都有现成的函数可以调用，为程序设计者提供了极大方便。
对于串查找， Robert S.Boyer 和 J.Strother Moore 在 1977 年实现了一个非常高效的串查找算法 BoyerMoore ，使用简单的有限状态自动机 FMS 控制，在目标串中移动， FSM 用一个数组来表示。
算法原理 , 我在这里不做详细的解说了 . 朋友们可以找找相关的资料 . 本人主要是参考 Scott Robert Ladd 著的 Java Algorithms 中的 BoyerMoore 算法 .
本文根据此算法介绍在 C# 中的实现。
算法测试结果如下图 :
具体算法如下 :
using System;
namespace stringsearch
{
///
1<summary>
2
3/// 字符串搜索的基本抽象类
4
5/// </summary>
public abstract class StringSearchTool
{
public enum Search
{
NOT_FOUND,
SEARCH_EXACT,
SEARCH_CASELESS
}
protected Search search;
protected String pattern;
public string Pattern
{
get
{
return pattern;
}
set
{
// 大小写暂时无用处
if (search==Search.SEARCH_CASELESS)
{
pattern= value ;
pattern.ToUpper();
}
else
{
pattern= value ;
}
}
}
public StringSearchTool()
{
search=Search.SEARCH_CASELESS;
pattern= null ;
}
public StringSearchTool( string p)
{
search=Search.SEARCH_CASELESS;
pattern=p;
}
public StringSearchTool( string p,Search type)
{
search=type;
pattern=p;
}
public int getPatternLength()
{
return pattern.Length;
}
public Search getSearchType()
{
return search;
}
public int find( string target)
{
return find(target,0);
}
public abstract int find( string target, int start);
}
}
BoyerMoore 算法
using System;
namespace stringsearch
{
///
1<summary>
2
3///
4
5/// </summary>
public class BoyerMoore : stringsearch.StringSearchTool
{
protected int [] delta;
private static readonly int DELTA_SIZE=65536;
public BoyerMoore(): base ()
{
}
public BoyerMoore( string p): base (p)
{
}
public BoyerMoore( string p,Search type): base (p,type)
{
}
public override int find( string target, int start)
{
if ((pattern== null )||(start<0))
return ( int )Search.NOT_FOUND;
String target2;
//if(search==Search.SEARCH_CASELESS)
// target2=target.ToUpper();
//else
target2=target;
int t=start+pattern.Length;
while (t<=target2.Length)
{
int p=pattern.Length;
while (pattern[p-1]==target2[t-1])
{
if (p>1)
{
--p;
--t;
}
else
{
return t-1;
}
}
t+=delta[( int )target2[t-1]];
}
return ( int )Search.NOT_FOUND;
}
public new string Pattern
{
get
{
return base .Pattern;
}
set
{
base .Pattern= value ;
int n;
<P class=MsoNormal