C++에서 "THE"로 끝나지 않는 문자열용 DFA?

Deterministic Finite Automaton(DFA)을 사용하여 하위 문자열 "THE"로 끝나지 않는 문자열을 찾습니다. "tHe", "The" ,"TheE" 등과 같은 하위 문자열 "THE"의 변형이 문자열 끝에 있으면 안 된다는 점을 명심해야 합니다.

먼저 dfa 변수를 정의하고 상태를 추적하는 0으로 초기화합니다. 일치하는 각 문자마다 증가합니다.

int dfa = 0;

begin(char c) 메소드는 문자를 받아서 't' 또는 'T'인지 확인하고 첫 번째 상태 즉 1로 이동합니다.

void begin(char c){
   if (c == 't' || c == 'T')
   dfa = 1;
}

firstState(char c) 메서드는 첫 번째 문자를 확인하고 해당 값에 따라 dfa를 할당합니다. c가 't' 또는 'T'이면 첫 번째 상태로 이동하고 c가 'h' 또는 'H'이면 두 번째 상태로 이동하고 마지막으로 다른 문자이면 시작 상태, 즉 0으로 이동합니다.

void firstState(char c){
   if (c == 't' || c == 'T')
      dfa = 1;
   else if (c == 'h' || c == 'H')
      dfa = 2;
   else
      dfa = 0;
}

secondState(char c)는 문자를 취하며 DFA 두 번째 상태를 확인하는 데 사용됩니다. 전달된 문자가 'E' 또는 'e'와 같으면 시작 상태인 0에 대해 세 번째 상태로 이동합니다.

void secondState(char c){
   if (c == 'e' || c == 'E')
      dfa = 3;
   else
      dfa = 0;
}

thirdState(char c)는 문자를 받아 DFA의 세 번째 상태를 확인하는 데 사용됩니다. 문자가 't' 또는 'T'와 같으면 첫 번째 상태(1)로 이동하고 그렇지 않으면 시작 상태, 즉 0으로 이동합니다.

void thirdState(char c){
   if (c == 't' || c == 'T')
      dfa = 1;
   else
      dfa = 0;
}

isAccepted(string str)는 테스트할 문자열을 매개변수로 사용합니다. len 변수는 문자열의 길이를 저장합니다. for 루프는 문자열 길이까지 반복됩니다. dfa =0이면 start(char c) 함수가 호출되고 dfa가 1이면 firstState(char c) 함수가 호출되고 dfa가 2이면 secondState(char c) 함수가 호출되고 dfa가 '이면 ' t 1,2,3 그러면 thirdState(char c) 함수가 호출됩니다. dfa가 3인지 아닌지에 따라 true 또는 false를 반환합니다. dfa가 3과 같지 않으면 문자열이 허용되고 그렇지 않으면 허용되지 않습니다.

bool isAccepted(string str){
   int len = str.length();
   for (int i=0; i < len; i++) {
      if (dfa == 0)
         begin(str[i]);
      else if (dfa == 1)
         firstState(str[i]);
      else if (dfa == 2)
         secondState(str[i]);
      else
         thirdState(str[i]);
   }
   return (dfa != 3);
}

예

"THE"로 끝나지 않는 문자열에 대한 DFA를 찾기 위해 다음 구현을 살펴보겠습니다. -

#include <iostream>
#include <string>
using namespace std;
int dfa = 0;
void begin(char c){
   if (c == 't' || c == 'T')
      dfa = 1;
}
void firstState(char c){
   if (c == 't' || c == 'T')
      dfa = 1;
   else if (c == 'h' || c == 'H')
      dfa = 2;
   else
      dfa = 0;
}
void secondState(char c){
   if (c == 'e' || c == 'E')
      dfa = 3;
   else
      dfa = 0;
}
void thirdState(char c){
   if (c == 't' || c == 'T')
      dfa = 1;
   else
      dfa = 0;
}
bool isAccepted(string str){
   int len = str.length();
   for (int i=0; i < len; i++) {
      if (dfa == 0)
         begin(str[i]);
      else if (dfa == 1)
         firstState(str[i]);
      else if (dfa == 2)
         secondState(str[i]);
      else
         thirdState(str[i]);
   }
   return (dfa != 3);
}
int main(){
   string str = "helloForTheWorld";
   if (isAccepted(str) == true)
      cout<<"The string "<<str<<" is accepted ";
   else
      cout<<"The string "<<str<<" is not accepted";
   return 0;
}

출력

위의 코드는 다음 출력을 생성합니다 -

The string helloForTheWorld is accepted