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’ 我们转到第二个状态，最后如果它是其他字符，那么我们转到起始状态，即 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 不是 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<<"The string "<<str<<" is accepted ";
else
cout<<"The string "<<str<<" is not accepted";
return 0;
}
输出
上述代码将产生以下输出 −
The string helloForTheWorld is accepted
