C#，字符串匹配（模式搜索）有限自动机（Finite Automata）算法的源代码

一、有限状态自动机

图中两个圆圈，也叫节点，用于表示状态，从图中可以看成，它有两个状态，分别叫0和1。从每个节点出发，都会有若干条边。当处于某个状态时，如果输入的字符跟该节点出发的某条边的内容一样，那么就会引起状态的转换。例如，如果当前状态处于0，输入是字符a，那么状态机就会从状态0进入状态1。如果当前状态是1，输入字符是b或a，那么，状态机就会从状态1进入状态0。如果当前所处的状态，没有出去的边可以应对输入的字符，那么状态机便会进入到错误状态。例如，如果当前处于状态0，输入字符是c，那么状态机就会出错，因为从状态0开始，没有哪条边对应的字符是c。

本代码的运行效果：

二、有限状态机用于字符串匹配（模式搜索）

假定要查找的字符串为P=”ABABCABAB”，被查找的文本为T=”ABABDABACDABABCABAB”。 一次读入T的一个字符，用S表示当前读入的T的字符，一开始读入一个字符，于是S=a。然后看看，从P开始，连续几个字符所构成的字符串可以成为S的后缀，由于当前S只有一个字符A，于是从P开始，连续1个字符所形成的字符串”A”，可以作为S的后缀。把这个字符串的长度记为k，于是此时k 等于1。继续从T中读入字符，于是S=”AB”， 此时，从P开始，连续两个字符所构成的字符串”AB”可以作为S的后缀，于是k = 2。如此反复。

利用有限状态机便可以构造这样的后缀序列。

源代码：

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

namespace Legalsoft.Truffer.Algorithm
{
?? ?public static partial class PatternSearch
?? ?{
?? ??? ?/// <summary>
?? ??? ?/// 下一个状态
?? ??? ?/// </summary>
?? ??? ?/// <param name="patternArray"></param>
?? ??? ?/// <param name="M"></param>
?? ??? ?/// <param name="state"></param>
?? ??? ?/// <param name="x"></param>
?? ??? ?/// <returns></returns>
?? ??? ?public static int NextState(char[] patternArray, int M, int state, int x)
?? ??? ?{
?? ??? ??? ?if (state < M && (char)x == patternArray[state])
?? ??? ??? ?{
?? ??? ??? ??? ?return state + 1;
?? ??? ??? ?}

?? ??? ??? ?for (int ns = state; ns > 0; ns--)
?? ??? ??? ?{
?? ??? ??? ??? ?if (patternArray[ns - 1] == (char)x)
?? ??? ??? ??? ?{
? ? ? ? ? ? ? ? ? ? int i;
?? ??? ??? ??? ??? ?for (i = 0; i < ns - 1; i++)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?if (patternArray[i] != patternArray[state - ns + 1 + i])
?? ??? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?if (i == ns - 1)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?return ns;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ?}

?? ??? ??? ?return 0;
?? ??? ?}

?? ??? ?/// <summary>
?? ??? ?/// 计算TF表
?? ??? ?/// </summary>
?? ??? ?/// <param name="patternArray"></param>
?? ??? ?/// <param name="M"></param>
?? ??? ?/// <returns></returns>
?? ??? ?public static int[,] Compute_TF(char[] patternArray, int M)
?? ??? ?{
?? ??? ??? ?int[,] TF = new int[M + 1, ALPHA_CODE_MAX];
?? ??? ??? ?for (int state = 0; state <= M; ++state)
?? ??? ??? ?{
?? ??? ??? ??? ?for (int x = 0; x < ALPHA_CODE_MAX; ++x)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?TF[state, x] = NextState(patternArray, M, state, x);
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?return TF;
?? ??? ?}

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

?? ??? ??? ?int M = pattern.Length;
?? ??? ??? ?int N = text.Length;
?? ??? ??? ?int[,] TF = Compute_TF(pattern.ToCharArray(), M);//, TF);
?? ??? ??? ?int state = 0;
?? ??? ??? ?for (int i = 0; i < N; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?state = TF[state, text[i]];
?? ??? ??? ??? ?if (state == M)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?matchs.Add((i - M + 1));
?? ??? ??? ??? ?}
?? ??? ??? ?}

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

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

POWER BY TRUFFER.CN

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

namespace Legalsoft.Truffer.Algorithm
{
?? ?public static partial class PatternSearch
?? ?{
?? ??? ?/// <summary>
?? ??? ?/// 下一个状态
?? ??? ?/// </summary>
?? ??? ?/// <param name="patternArray"></param>
?? ??? ?/// <param name="M"></param>
?? ??? ?/// <param name="state"></param>
?? ??? ?/// <param name="x"></param>
?? ??? ?/// <returns></returns>
?? ??? ?public static int NextState(char[] patternArray, int M, int state, int x)
?? ??? ?{
?? ??? ??? ?if (state < M && (char)x == patternArray[state])
?? ??? ??? ?{
?? ??? ??? ??? ?return state + 1;
?? ??? ??? ?}

?? ??? ??? ?for (int ns = state; ns > 0; ns--)
?? ??? ??? ?{
?? ??? ??? ??? ?if (patternArray[ns - 1] == (char)x)
?? ??? ??? ??? ?{
? ? ? ? ? ? ? ? ? ? int i;
?? ??? ??? ??? ??? ?for (i = 0; i < ns - 1; i++)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?if (patternArray[i] != patternArray[state - ns + 1 + i])
?? ??? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?if (i == ns - 1)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?return ns;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ?}

?? ??? ??? ?return 0;
?? ??? ?}

?? ??? ?/// <summary>
?? ??? ?/// 计算TF表
?? ??? ?/// </summary>
?? ??? ?/// <param name="patternArray"></param>
?? ??? ?/// <param name="M"></param>
?? ??? ?/// <returns></returns>
?? ??? ?public static int[,] Compute_TF(char[] patternArray, int M)
?? ??? ?{
?? ??? ??? ?int[,] TF = new int[M + 1, ALPHA_CODE_MAX];
?? ??? ??? ?for (int state = 0; state <= M; ++state)
?? ??? ??? ?{
?? ??? ??? ??? ?for (int x = 0; x < ALPHA_CODE_MAX; ++x)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?TF[state, x] = NextState(patternArray, M, state, x);
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?return TF;
?? ??? ?}

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

?? ??? ??? ?int M = pattern.Length;
?? ??? ??? ?int N = text.Length;
?? ??? ??? ?int[,] TF = Compute_TF(pattern.ToCharArray(), M);//, TF);
?? ??? ??? ?int state = 0;
?? ??? ??? ?for (int i = 0; i < N; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?state = TF[state, text[i]];
?? ??? ??? ??? ?if (state == M)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?matchs.Add((i - M + 1));
?? ??? ??? ??? ?}
?? ??? ??? ?}

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