Solarsoft
introduction
Any valid application has processing text information, such as editing, typography, information retrieval, document analysis, knowledge excavation, language identification, etc., all need to use the extraction and positioning of text strings. There are ready-made functions in many programming languages to be called, providing a great convenience for program designers.
For string finding, Robert S.Boyer and J. Strother Moore implements a very efficient string of string of Boyermoore in 1977, using simple limited state automaton control, moving in the target string, FSM is represented by an array.
The principle of algorithm, I don't have a detailed explanation here. Friends can find relevant information. I am mainly referring to the BoyErmoore algorithm in Java Algorithms in Scott Robert Ladd.
This article describes the implementation in C # in accordance with this algorithm.
The results of the algorithm test are as follows:
The specific algorithm is as follows: USING SYSTEM;
Namespace stringsearch
{
///
/// String Search Basic Abstract Class
///
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
{
// Size is temporarily useless
IF (Search == Search.Search_caseless)
{
Pattern = Value;
Pattern.toupper ();
}
Else
{
Pattern = Value;
}
}
}
Public stringsearchtool ()
{
Search = search.search.Search_caseless;
Pattern = NULL;
}
Public StringSearchtool (String P)
{
Search = 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 found (String Target)
{
Return Find (Target, 0);
}
Public Abstract Int Find (String Target, int Start);
}
}
BoyerMoore Algorithm Using System;
Namespace stringsearch
{
///
///
///
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 found (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;
Delta = new int [DELTA_SIZE];
FOR (n = 0; n Delta [n] = pattern.length; For (n = 1; n Delta [(int) Pattern [N-1]] = pattern.length-n; Delta [(int) Pattern [Pattern.length-1] = 1; } } } } Test Code (Part): Private Void Button1_Click (Object Sender, System.EventArgs E) { String terget = label1.text; String pattern = textbox1.text; Boyermoore BM = New Boyermoore (); BM.PATTERN = Pattern; IF (BM.Find (Terget, 0)> 0) Messagebox.show (this, "Are you looking for" Pattern "?" "Congratulations!"); "); Else Messagebox.show (this, "did not find the text you look for in this passage!"); } Compiled has passed, there are some small vulnerabilities in the above design, and friends can modify the following.
