字符串的 DFA 在 C++ 中不以“THE”结尾？

使用确定性有限Automaton(DFA)来查找不以子字符串“THE”结尾的字符串。我们应该记住，子字符串“THE”的任何变体，如“tHe”、“The”、“TheE”等都不应该出现在字符串的末尾。

首先，我们定义我们的 dfa 变量并将其初始化为 0，以跟踪我们的状态。它在每个匹配的字符上递增。

int dfa = 0;

该begin(char c)方法接受一个字符并检查它是 't' 还是 'T' 并转到第一个状态i.e1。

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

该firstState(char c)方法检查第一个字符并根据该值分配 dfa。如果 c 是 't' 或 'T'，那么我们进入第一个状态，如果 c 是 'h' 或 'H'，我们进入第二个状态，最后如果它是其他字符，那么我们进入起始状态i.e0。

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'，则我们转到第三个状态，否则转到开始状态i.e0。

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

在thirdState(char c)需要一个字符，并用于检查所述第三DFA状态。如果字符等于 't' 或 'T'，则我们进入第一个状态 (1)，否则进入起始状态i.e0。

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 不是 1,2,3，则thirdState(char c)调用函数。我们根据 dfa 是否为 3 来返回 true 或 false。如果 dfa 不等于三，则接受该字符串，否则不接受。

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<<"字符串 "<<str<<" is accepted ";
   else
      cout<<"字符串 "<<str<<" is not accepted";
   return 0;
}

上面的代码将产生以下输出 -

字符串 helloForTheWorld is accepted