3

我需要能够处理一个或多个单词并验证它是否具有有效的音节。有一些可以使用的音节规则：

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

过渡是在超状态之间进行的。超级国家的每个成员都以相同的符号前进。没有这种转换的所有成员都将被丢弃。如果一个成员有两个可能的目的地，则两个都被添加到新的超级状态中。

您可能会注意到有些行非常相似。超状态 3 和 7 具有相同的转换。与 6 和 11，以及 8 和 13 一样。您可以将它们分别折叠成一个状态，然后更新索引。我不打算在这里证明这一点。

这可以很容易地编码成编程语言：

//                    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 回答