資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
