#include <iostream>
#include <cstring>
#include <string>
#define MAXSIZE 256
#define PATSIZE 10
using namespace std;
// pat = 'ABCAD' ==>
// state | A | B | C | D |
// 0 | 1 | 0 | 0 | 0 |
// 1 | 1 | 2 | 0 | 0 |
// 2 | 1 | 0 | 3 | 0 |
// 3 | 4 | 0 | 0 | 0 |
// 4 | 1 | 0 | 0 | 5 |
//
void constructFA(char pat[], int m, int FA[][MAXSIZE])
{
for(int i=0; i<m; i++)
{
FA[i][pat[0]] = 1;
FA[i][pat[i]] = i+1;
}
}
void findMatch(char txt[], int n, char pat[], int m, int FA[][MAXSIZE])
{
int state=0;
for(int i=0; i<n; i++)
{
state = FA[state][txt[i]];
if(state == m)
{
cout << "index=" << i << ": " << string(txt).substr(i,n-i+1)<< endl;
state = 0;
}
}
}
int main() {
// your code goes here
char txt[] = "This is a test. It is new.";
char pat[] = "is";
int FA[PATSIZE][MAXSIZE];
constructFA(pat, strlen(pat)-1, FA);
findMatch(txt, strlen(txt)-1, pat, strlen(pat)-1, FA);
return 0;
}
--------------------------------
output:
index=2: is is a test. It is new.
index=5: is a test. It is new.
index=19: is new.
