数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律学C++ 程序执行基于有限状态自动机的搜索
这是一个执行基于有限状态自动机的搜索的 C++ 程序。具有有限状态数的自动机称为有限状态自动机。这里，给定文本 text[0 … t-1]，以及给定图案 p[0 ... p-1]。我们必须在文本中找到该图案并打印其在各个索引处的所有出现。
算法
Begin Function void transitiontable(): 1) put the entries in first row and filled it up. All entries in first row are always 0 except the entry for p[0] character. Always we need to go to state 1. for p[0]. 2) Initialize longestprefixsuffix as 0. 3) for i = 1 to P. (Here P is the length of the pattern) a) Copy the entries from the row at index equal to longestprefixsuffix. b) Update the entry for p[i] character to i+1. c) Update longestprefixsuffix = TF[lps][pat[i]] where TT is the 2D array. End
示例
#include<iostream>
#include<cstring>
#define NO_OF_CHARS 512
using namespace std;
// builds the TF table which represents Finite Automata for a given pattern
void transitiontable(char *p, int P, int TT[][NO_OF_CHARS]) {
int i, longestprefixsuffix = 0, y;
// put entries in first row
for (y =0; y < NO_OF_CHARS; y++)
TT[0][y] = 0;
TT[0][p[0]] = 1;
// put entries in other rows
for (i = 1; i<= P; i++) { // Copy values from row at index longestprefixsuffix
for (y = 0; y < NO_OF_CHARS; y++)
TT[i][y] = TT[longestprefixsuffix][y];
// Update the entry
TT[i][p[i]] = i + 1;
// Update lps for next row to be filled
if (i < P)
longestprefixsuffix = TT[longestprefixsuffix][p[i]]; // TT is the 2D array which is being constructed.
}
}
//Prints all occurrences of pattern in text
void patternsearch(char *p, char *t) {
int P = strlen(p);
int T = strlen(t);
int TT[P+1][NO_OF_CHARS];
transitiontable(p, P, TT);
// process text over FA.
int i, j=0;
for (i = 0; i < T; i++) {
j = TT[j][t[i]];
if (j == P) {
cout<<"\n pattern is found at index: "<< i-P+1;
}
}
}
int main() {
char *text = "AABAA ABBAACCDD CCDDAABAA"; //take the text as input
char *pattern = "AABAA"; //take the pattern as input
patternsearch(pattern, text);
getchar();
return 0;
}输出
pattern is found at index: 0 pattern is found at index: 20
更新于： 2019-07-30
687 浏览
广告