3

1つまたは複数の単語を処理し、有効な音節があることを確認できる必要があります。使用できる音節規則がいくつかあります。

V CV VC CVC CCV CCCV CVCC

ここで、Vは母音、Cは子音です。例えば、

pronunciation (5 Pro-nun-ci-a-tion; CCV-CVC-CV-V-CVC)

または、使用できる単純なコード、またはC ++のライブラリはありますか？クラスでは、二分探索木やハッシュテーブルなどについて話していますが、実際には関係がわかりません。助けていただければ幸いです、ありがとう。

4

1 に答える 1

4

完全なパターン文字列を収集したときはいつでも、それを破棄して新しいパターン文字列への収集を開始するか、それを保持してより長いパターン文字列を取得しようとすることができます。現在の文字列を保持するか破棄するかは（入力文字列の残りの部分を調べずに）事前にわからないため、両方の可能性を念頭に置く必要があります。

これを追跡できるステートマシンを構築できます。基本状態は、これまでに調べた文字のシーケンスによって識別されます。

State   C           V
""      {"C"}       {"V",""}
"C"     {"CC"}      {"CV",""}
"CC"    {"CCC"}     {""}
"CCC"   {}          {""}
"CV"    {"CVC",""}  {}
"CVC"   {""}        {}
"V"     {""}        {}

どのアクションを実行するかが常にわからないため、一度にいくつかの可能な状態になる可能性があります。これらの可能な状態のセットは、スーパー状態を形成します。

Index   Super-state        C    V
    0   {}                 0    0   Fail 
    1   {""}               2    9   Accept 
    2   {"C"}              3    8
    3   {"CC"}             4    1
    4   {"CCC"}            0    1
    5   {"","C"}           6   13   Accept
    6   {"C","CC"}         7    8
    7   {"CC","CCC"}       4    1
    8   {"","CV"}         12    9   Accept
    9   {"","V"}           5    9   Accept
   10   {"","C","CC"}     11   13   Accept
   11   {"C","CC","CCC"}   7    8
   12   {"","C","CVC"}    10   13   Accept
   13   {"","CV","V"}     12    9   Accept

遷移はスーパーステート間です。スーパーステートの各メンバーは、同じシンボルで進められます。そのような移行のないすべてのメンバーは破棄されます。メンバーに2つの可能な宛先がある場合、両方が新しいスーパーステートに追加されます。

一部の行が非常に似ていることに気付くかもしれません。スーパーステート3と7の遷移は同じです。6と11、および8と13も同様です。これらをそれぞれ1つの状態にまとめて、インデックスを更新できます。ここではそれを説明しません。

これは、プログラミング言語に簡単にエンコードできます。

//                    index = 0  1  2  3  4   5  6  7   8  9  10  11  12  13
int[] consonant = new int[] { 0, 2, 3, 4, 0,  6, 7, 4, 12, 5, 11,  7, 10, 12 };
int[] vocal = new int[] {     0, 9, 8, 1, 1, 13, 8, 1,  9, 9, 13,  8, 13,  9 };
int[] accept = new int[] {    0, 1, 0, 0, 0,  1, 0, 0,  1, 1,  1,  0,  1,  1 };
int startState = 1;
int failState = 0;

bool CheckWord(string word)
{
    int state = startState;
    foreach (char c in word)
    {
        if (IsVocal(c))
        {
            state = vocal[state];
        }
        else if (IsConsonant(c))
        {
            state = consonant[state];
        }
        if (state == failState) return false;
    }
    return accept[state] != 0;
}

例：

> CheckWord("pronunciation")
true

> CheckWord("pronunciationn")
false
于 2012-10-25T22:30:45.743 に答える