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

2023-06-21 12:29:03 85

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

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

int dfa = 0;

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

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

该firstState(charc)方法检查第一个字符并根据该值分配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(charc)需要一个字符，并用于检查所述DFA第二状态。如果传递的字符等于'E'或'e'，则我们转到第三个状态，否则转到开始状态i.e0。

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

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

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

将isAccepted(stringstr)要测试的字符串作为参数。len变量存储字符串的长度。for循环迭代直到字符串长度。如果dfa=0，则start(charc)调用函数，如果dfa等于1，则firstState(charc)调用函数，如果dfa等于2，则secondState(charc)调用函数，如果dfa不是1,2,3，则thirdState(charc)调用函数。我们根据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 
#include 
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<<"字符串 "<输出结果
上面的代码将产生以下输出-
字符串 helloForTheWorld is accepted

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

示例

热门推荐

随机推荐