数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学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 不等于 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
264 次浏览
