有限自动机的高效构建
什么是有限自动机？
有限自动机是一种用于识别输入文本中模式的数学计算模型。它由一组状态及其之间的转换组成。该机器可以接受或拒绝输入字符串，这表明它只有两个状态。
用于模式匹配的有限自动机
要使用有限自动机进行模式匹配，我们需要构建一个仅接受与给定模式匹配的字符串的有限自动机。假设我们创建了一个具有四个状态的有限自动机，即 q0、q1、q2 和 q3。初始状态为"q0"，最终状态为"q3"。 转换用模式的字符标记。
现在，我们从起始状态开始匹配，并根据输入符号从左到右读取字符串，遵循转换。如果读取整个字符串后到达最终状态，则该字符串与模式匹配。否则，字符串与模式不匹配。
以下是输入输出场景，以增强我们对问题的理解 −
输入： 主字符串："ABAAABCDBBABCDDEBCABC" 模式："ABC" 输出： 在位置 4 处找到模式 在位置 10 处找到模式 在位置 18 处找到模式
给定输入字符串"ABAAABCDBBABCDDEBCABC"和模式"ABC"，我们使用有限自动机程序在字符串中搜索该模式的出现次数。程序在索引位置 4、10 和 18 处识别出该模式。
示例
现在，让我们实现有限自动机方法，以解决不同编程语言中的模式匹配问题 −
#include <stdio.h>
#include <string.h>
#define MAXCHAR 256
// 根据给定的模式填充有限自动机转换表
void fillTransitionTable(const char *pattern, int transTable[][MAXCHAR]) {
int longPS = 0;
// 将所有字符的第一个状态初始化为 0
for (int i = 0; i < MAXCHAR; i++) {
transTable[0][i] = 0;
}
// 对于模式的第一个字符，移动到第一个状态
transTable[0][(int)pattern[0]] = 1;
// 对于模式的其余字符，使用前缀和后缀创建状态
for (int i = 1; i <= strlen(pattern); i++) {
// 将值从 LPS 长度复制到当前状态
for (int j = 0; j < MAXCHAR; j++)
transTable[i][j] = transTable[longPS][j];
// 对于当前模式字符，移动到下一个状态
transTable[i][(int)pattern[i]] = i + 1;
// 更新下一个状态的 LPS 长度
if (i < strlen(pattern))
longPS = transTable[longPS][(int)pattern[i]];
}
}
// 使用有限自动机方法在主字符串中搜索模式
void FAPatternSearch(const char *mainString, const char *pattern, int array[], int *index) {
int patLen = strlen(pattern);
int strLen = strlen(mainString);
// 为模式创建转换表
int transTable[patLen + 1][MAXCHAR];
fillTransitionTable(pattern, transTable);
int presentState = 0;
// 迭代主字符串
for (int i = 0; i <= strLen; i++) {
// 如果转换可行，则转到下一个状态
presentState = transTable[presentState][(int)mainString[i]];
// 如果当前状态是最终状态，则发现模式
if (presentState == patLen) {
(*index)++;
array[(*index)] = i - patLen + 1;
}
}
}
int main() {
const char *mainString = "ABAAABCDBBABCDDEBCABC";
// 要搜索的模式
const char *pattern = "ABC";
int locArray[strlen(mainString)];
int index = -1;
// 调用模式搜索功能
FAPatternSearch(mainString, pattern, locArray, &index);
// 打印结果
for (int i = 0; i <= index; i++) {
printf("Pattern found at position: %d
", locArray[i]);
}
return 0;
}
#include<iostream>
#define MAXCHAR 256
using namespace std;
// 根据给定的模式填充有限自动机转换表
void fillTransitionTable(string pattern, int transTable[][MAXCHAR]) {
int longPS = 0;
// 将所有字符的第一个状态初始化为 0
for (int i = 0; i < MAXCHAR; i++) {
transTable[0][i] = 0;
}
// 对于模式的第一个字符，移动到第一个状态
transTable[0][pattern[0]] = 1;
// For rest of the characters, create states using prefix and suffix
for (int i = 1; i<= pattern.size(); i++) {
// 将值从 LPS 长度复制到当前状态
for (int j = 0; j < MAXCHAR ; j++)
transTable[i][j] = transTable[longPS][j];
// 对于当前模式字符，移动到下一个状态
transTable[i][pattern[i]] = i + 1;
// 更新下一个状态的 LPS 长度
if (i < pattern.size())
longPS = transTable[longPS][pattern[i]];
}
}
// 使用有限自动机方法在主字符串中搜索模式
void FAPatternSearch(string mainString, string pattern, int array[], int *index) {
int patLen = pattern.size();
int strLen = mainString.size();
// 为模式创建转换表
int transTable[patLen+1][MAXCHAR];
fillTransitionTable(pattern, transTable);
int presentState = 0;
// 迭代主字符串
for(int i = 0; i<=strLen; i++) {
// 如果转换可行，则转到下一个状态
presentState = transTable[presentState][mainString[i]];
// 如果当前状态是最终状态，则发现模式
if(presentState == patLen) {
(*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;
}
}
public class Main {
static final int MAXCHAR = 256;
// 根据给定的模式填充有限自动机转换表
public static void fillTransitionTable(String pattern, int[][] transTable) {
int longPS = 0;
// 将所有字符的第一个状态初始化为 0
for (int i = 0; i < MAXCHAR; i++) {
transTable[0][i] = 0;
}
// 对于模式的第一个字符，移动到第一个状态
transTable[0][pattern.charAt(0)] = 1;
// For rest of the characters, create states using prefix and suffix
for (int i = 1; i < pattern.length(); i++) {
// 将值从 LPS 长度复制到当前状态
for (int j = 0; j < MAXCHAR; j++)
transTable[i][j] = transTable[longPS][j];
// 对于当前模式字符，移动到下一个状态
transTable[i][pattern.charAt(i)] = i + 1;
// 更新下一个状态的 LPS 长度
longPS = transTable[longPS][pattern.charAt(i)];
}
}
// 使用有限自动机方法在主字符串中搜索模式
public static void FAPatternSearch(String mainString, String pattern, int[] array, int[] index) {
int patLen = pattern.length();
int strLen = mainString.length();
// 为模式创建转换表
int[][] transTable = new int[patLen + 1][MAXCHAR];
fillTransitionTable(pattern, transTable);
int presentState = 0;
// 迭代主字符串
for (int i = 0; i < strLen; i++) {
// 如果转换可行，则转到下一个状态
presentState = transTable[presentState][mainString.charAt(i)];
// 如果当前状态是最终状态，则发现模式
if (presentState == patLen) {
index[0]++;
array[index[0]] = i - patLen + 1;
}
}
}
public static void main(String[] args) {
String mainString = "ABAAABCDBBABCDDEBCABC";
// 要搜索的模式
String pattern = "ABC";
int[] locArray = new int[mainString.length()];
int[] index = { -1 };
// 调用模式搜索方法
FAPatternSearch(mainString, pattern, locArray, index);
// 打印结果
for (int i = 0; i <= index[0]; i++) {
System.out.println("Pattern found at position: " + locArray[i]);
}
}
}
MAXCHAR = 256
# 根据给定的模式填充有限自动机转换表
def fillTransitionTable(pattern, transTable):
longPS = 0
# 将所有字符的第一个状态初始化为 0
for i in range(MAXCHAR):
transTable[0][i] = 0
# 对于模式的第一个字符，移动到第一个状态
transTable[0][ord(
pattern[0])] = 1
# 对于模式的其余字符，使用前缀和后缀创建状态
for i in range(1, len(pattern)):
# 将值从 LPS 长度复制到当前状态
for j in range(MAXCHAR):
transTable[i][j] = transTable[longPS][j]
# 对于当前模式字符，移动到下一个状态
transTable[i][ord(pattern[i])] = i + 1
# 更新下一个状态的 LPS 长度
longPS = transTable[longPS][ord(
pattern[i]
)]
# 使用有限自动机方法在主字符串中搜索模式
def FAPatternSearch(mainString, pattern, array, index):
patLen = len(pattern)
strLen = len(mainString)
# 为每个模式创建一个转换表
transTable = [[0] * MAXCHAR for _ in range(patLen + 1)
]
fillTransitionTable(pattern, transTable)
presentState = 0
# 迭代主字符串
for i in range(strLen):
# 如果转换可行，则转到下一个状态
presentState = transTable[presentState][ord(
mainString[i]
)]
# 如果当前状态是最终状态，则发现模式
if presentState == patLen:
index[0] += 1
array[index[0]] = i - patLen + 1
mainString = "ABAAABCDBBABCDDEBCABC"
pattern = "ABC"
locArray = [0] * len(mainString)
index = [-1]
#调用模式搜索功能
FAPatternSearch(mainString, pattern, locArray, index)
for i in range(index[0] + 1):
print("Pattern found at position:", locArray[i])
输出
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
