패턴 검색을 위한 유한 오토마타 알고리즘을 위한 C++ 프로그램

이 글에서는 패턴 검색을 위한 유한 자동 알고리즘을 실행하는 프로그램에 대해 논의할 것입니다.

텍스트[0...n-1]와 패턴[0...m-1]이 제공됩니다. text[]에서 pattern[]의 모든 항목을 찾아야 합니다.

이를 위해 우리는 text[]를 전처리하고 그것을 나타내기 위해 2차원 배열을 만들 것입니다. 그 다음에는 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