C ++で「THE」で終わらない文字列のDFA？

決定性有限オートマトン（DFA）を使用して、部分文字列「THE」で終わっていない文字列を検索します。 「tHe」、「The」、「ThE」などのサブストリング「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」の場合は2番目の状態になり、最後に他の文字の場合は開始状態、つまり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の2番目の状態をチェックするために使用されます。渡された文字が「E」または「e」に等しい場合は、3番目の状態に進みます。それ以外の場合は、最初の状態、つまり0に進みます。

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

thirdState（char c）は文字を取り、DFAの3番目の状態をチェックするために使用されます。文字が「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がn'の場合は呼び出されます。 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