有限自动机的高效构造
通过构造有限自动机，我们可以简单地在文本中执行模式搜索。首先，我们必须填充2D数组以制作有限自动机的过渡表。创建表后，搜索过程很简单。通过从自动机的第一个状态开始，当我们到达最终状态时，这意味着在字符串中找到了模式。
对于有限自动机构造，时间复杂度为O（M*K），M为模式长度，K为许多不同的字符。主模式搜索的复杂度为O(n)。
输入输出
Input: Main String: “ABAAABCDBBABCDDEBCABC”, Pattern “ABC” Output: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
算法
fillTransTable(pattern,transTable)
输入-模式和过渡表以填充过渡
输出-填充的过渡表
Begin
longPS := 0
clear all entries of transition table with 0
transTable[0, patter[0]] = 1 //for the first character of the pattern
for index of all character i present in pattern, do
for all possible characters, do
transTable[i,j] := transTable[longPS, j]
done
transTable[i, pattern[i]] := i+1
if i < pattern size, then
longPS := transTable[longPS, pattern[i]]
done
EndpatternSearch（文本，图案）
输入-主要文本和模式
输出-索引，找到模式。
Begin
patLen := pattern length
strLen := string length
call fillTransTable(pattern, transTable)
present := 0
for all character’s index i of text, do
present := transTable[present, text[i]]
if present = patLen, then
print the location (i – patLen +1) as there is the pattern
done
End示例
#include<iostream>
#define MAXCHAR 256
using namespace std;
void fillTransitionTable(string pattern, int transTable[][MAXCHAR]) {
int longPS = 0;
for (int i = 0; i < MAXCHAR; i++) {
transTable[0][i] = 0; // create entries for first state
}
transTable[0][pattern[0]] = 1; //move to first state for first character
for (int i = 1; i<= pattern.size(); i++) {
for (int j = 0; j < MAXCHAR ; j++) // update states using prefix and suffix
transTable[i][j] = transTable[longPS][j];
transTable[i][pattern[i]] = i + 1;
if (i < pattern.size())
longPS = transTable[longPS][pattern[i]]; //update longest prefix and suffix for next states
}
}
void FAPatternSearch(string mainString, string pattern, int array[], int *index) {
int patLen = pattern.size();
int strLen = mainString.size();
int transTable[patLen+1][MAXCHAR]; //create transition table for each pattern
fillTransitionTable(pattern, transTable);
int presentState = 0;
for(int i = 0; i<=strLen; i++) {
presentState = transTable[presentState][mainString[i]]; //move to next state is transition is possible
if(presentState == patLen) { //when present state is the final state, pattern found
(*index)++;
array[(*index)] = i - patLen + 1 ;
}
}
}
int main() {
string mainString = "ABAAABCDBBABCDDEBCABC";
string pattern = "ABC";
int locArray[mainString.size()];
int index = -1;
FAPatternSearch(mainString, pattern, locArray, &index);
for(int i = 0; i <= index; i++) {
cout << "Pattern found at position: " << locArray[i]<<endl;
}
}输出结果
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18