C++で「THE」で終わらない文字列を判定するDFAの実装方法

決定性有限オートマトン（DFA：Deterministic Finite Automaton）を使うと、「THE」という部分文字列で終わらない文字列を効率的に判定できます。ここで注意すべき点は、「tHe」「The」「ThE」のように大文字・小文字が異なるバリエーションも含めて、文字列の末尾に「THE」が現れてはならないということです。

本記事では、C++によるDFAの実装手順を段階的に解説します。

DFAの状態管理の基本

まず、現在の状態を追跡するためのdfa変数を定義し、0で初期化します。この変数は、入力文字との照合が進むごとに次の状態へと遷移していきます。

int dfa = 0;

開始状態への遷移：begin(char c)

begin(char c)メソッドは、1文字を受け取り、それが 't' または 'T' であるかを判定します。該当する場合は、最初の状態（1）へ遷移します。

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

第1状態の処理：firstState(char c)

firstState(char c)メソッドは、入力された文字に応じて状態を更新します。c が 't' または 'T' なら第1状態（1）へ、'h' または 'H' なら第2状態（2）へ、それ以外の文字であれば開始状態（0）へ戻ります。

void firstState(char c){
    if (c == 't' || c == 'T')
        dfa = 1;
    else if (c == 'h' || c == 'H')
        dfa = 2;
    else
        dfa = 0;
}

第2状態の処理：secondState(char c)

secondState(char c)メソッドは、DFAの第2状態における遷移を担当します。渡された文字が 'e' または 'E' と一致すれば第3状態（3）へ進み、そうでなければ開始状態（0）へ戻ります。

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

第3状態の処理：thirdState(char c)

thirdState(char c)メソッドは、DFAの第3状態における遷移を処理します。ここまでで「TH」まで一致している状態です。次の文字が 't' または 'T' であれば第1状態（1）へ遷移し、新しい候補の開始として扱います。それ以外の場合は開始状態（0）へ戻ります。

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

文字列全体の判定：isAccepted(string str)

isAccepted(string str)は、判定対象の文字列を引数として受け取ります。変数lenに文字列の長さを格納し、forループで先頭から1文字ずつ処理を進めます。

• dfa == 0 のとき → begin(char c) を呼び出し
• dfa == 1 のとき → firstState(char c) を呼び出し
• dfa == 2 のとき → secondState(char c) を呼び出し
• 上記以外のとき → thirdState(char c) を呼び出し

すべての文字を処理した後、dfaが3かどうかによって true / false を返します。dfaが3でなければ文字列は受理され、3であれば「THE」で終わっているため拒否されます。

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

この例では、文字列「helloForTheWorld」は「THE」で終わっていないため、正しく受理されていることが確認できます。このようにDFAを用いれば、文字列を一度走査するだけで末尾パターンの判定が可能になり、計算量は文字数に対して線形時間 O(n) で済むというメリットがあります。