产品展示网站模板源码,商业网站建设的方法,一个网站做seo,导入视频生成3d动画一、有限状态自动机 图中两个圆圈#xff0c;也叫节点#xff0c;用于表示状态#xff0c;从图中可以看成#xff0c;它有两个状态#xff0c;分别叫0和1。从每个节点出发#xff0c;都会有若干条边。当处于某个状态时#xff0c;如果输入的字符跟该节点出发的某条边的内…一、有限状态自动机 图中两个圆圈也叫节点用于表示状态从图中可以看成它有两个状态分别叫0和1。从每个节点出发都会有若干条边。当处于某个状态时如果输入的字符跟该节点出发的某条边的内容一样那么就会引起状态的转换。例如如果当前状态处于0输入是字符a那么状态机就会从状态0进入状态1。如果当前状态是1输入字符是b或a那么状态机就会从状态1进入状态0。如果当前所处的状态没有出去的边可以应对输入的字符那么状态机便会进入到错误状态。例如如果当前处于状态0输入字符是c那么状态机就会出错因为从状态0开始没有哪条边对应的字符是c。
本代码的运行效果 二、有限状态机用于字符串匹配模式搜索
假定要查找的字符串为P”ABABCABAB”被查找的文本为T”ABABDABACDABABCABAB”。 一次读入T的一个字符用S表示当前读入的T的字符一开始读入一个字符于是Sa。然后看看从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 namepatternArray/param /// param nameM/param /// param namestate/param /// param namex/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 namepatternArray/param /// param nameM/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 nametext/param /// param namepattern/param /// returns/returns public static Listint Finite_Automata_Search(string text, string pattern) { Listint matchs new Listint(); 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 namepatternArray/param/// param nameM/param/// param namestate/param/// param namex/param/// returns/returnspublic 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 namepatternArray/param/// param nameM/param/// returns/returnspublic 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 nametext/param/// param namepattern/param/// returns/returnspublic static Listint Finite_Automata_Search(string text, string pattern){Listint matchs new Listint();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;}}
}
