用于模式搜索的有限自动机算法的C ++程序
在本文中，我们将讨论执行有限自动机算法以进行模式搜索的程序。
我们提供了一个text[0...n-1]和一个pattern[0...m-1]。我们必须找到text[]中所有pattern[]的出现。
为此，我们将预处理text[]并构建一个二维数组来表示它。之后，我们只需要遍历text[]的元素和自动机的不同状态即可。
示例
#include<stdio.h>
#include<string.h>
#define total_chars 256
int calc_nextstate(char *pat, int M, int state, int x) {
if (state < M && x == pat[state])
return state+1;
int ns, i;
for (ns = state; ns > 0; ns--) {
if (pat[ns-1] == x) {
for (i = 0; i < ns-1; i++)
if (pat[i] != pat[state-ns+1+i])
break;
if (i == ns-1)
return ns;
}
}
return 0;
}
//builds Finite Automata
void calc_TF(char *pat, int M, int TF[][total_chars]) {
int state, x;
for (state = 0; state <= M; ++state)
for (x = 0; x < total_chars; ++x)
TF[state][x] = calc_nextstate(pat, M, state, x);
}
//prints all occurrences of pattern in text
void calc_occur(char *pat, char *txt) {
int M = strlen(pat);
int N = strlen(txt);
int TF[M+1][total_chars];
calc_TF(pat, M, TF);
int i, state=0;
for (i = 0; i < N; i++){
state = TF[state][txt[i]];
if (state == M)
printf ("\n Given pattern is found at the index%d",i-M+1);
}
}
int main() {
char *txt = "AABCDAABBDCAABADAABDABAABA";
char *pat = "AABA";
calc_occur(pat, txt);
return 0;
}输出结果
Given pattern is found at the index 11 Given pattern is found at the index 22
热门推荐
10 冬至婆婆的祝福语简短
11 祝贺开业文案祝福语简短
12 股市祝福语简短10字
13 打牌翻盘祝福语简短
14 新疆新年祝福语大全简短
15 周末思念祝福语大全简短
16 拜年啦祝福语大全简短
17 中秋祝福语送朋友简短
18 宝宝周岁可乐祝福语简短