要搜索的有限状态机 "ABBA"

Question

我正在尝试编写 while switch case 有点代码，用于对有限状态机进行建模，该状态机搜索 A 和 B 的字符串以查看字符串 "ABBA" 是否存在。当我只输入 "ABBA" 时，它会像预期的那样输出 Word found!。但是，如果我输入 "AABBA" 它找不到单词并输出正确的消息。任何帮助表示赞赏。谢谢！

import java.util.*;
public class AB{
    public static void main(String args[]){
        Scanner input = new Scanner(System.in);
        String word = input.next();
        int current = 0;
        int status = 0;
        System.out.println("Starting to evaluate...");
        while(status != 4){
            for(int i = current; i < word.length(); i++){
                String part = word.substring(current, i + 1);
                switch(status){
                    case 0: //start
                        if(part.equals("A")){
                            status = 1;
                        }
                        else if(part.equals("B"){
                            status = 0; 
                            current = i;
                        }
                    break;
                    case 1: //A is there now
                        if(part.equals("AB")){
                            status = 2;
                        }
                        else if(part.equals("AA"){
                            status = 1;
                            current = 1;
                        }
                    break;
                    case 2: //AB is there now
                        if(part.equals("ABB")){
                            status = 3;
                        }
                        else if(part.equals("ABA"){
                            status = 1;
                            current = 1;
                        }
                    break;
                    case 3: //ABB is there now
                        if(part.equals("ABBA")){
                            status = 4;
                            System.out.println("Word found!");
                        }
                        else if(part.equals("ABBB"){
                            status = 0;
                            current = i;
                        }
                    break;
                }
            }
        }
    }
}

Answer 1

我在您的方法中看到的无效之处在于您实际上没有使用状态机的功能。首先，您应该了解是什么驱动您的机器通过这些状态。在您的示例中，输入字符串的每个连续字母都可以。由于您已经选择了一个状态，您现在应该检查下一个符号会将您的机器切换到哪个状态。让我建议以下实现..

这是状态图：

这是实现图表的代码：

public boolean abbaMatcher(String abba)
{
    int state = 0;
    int symbol = 0;


    while (symbol < abba.length()){
        char c = abba.charAt(symbol);
        switch (state){
            case 0: if(c == 'a'){
                        state = 1;
                    }else{
                        state = 0;
                    };
                    break;
            case 1: if(c == 'b'){
                        state = 2;
                    }else{
                        state = 1;
                    };
                    break;
            case 2: if(c == 'b'){
                        state = 3;
                    }else{
                        state = 1;
                    };
                    break;
            case 3: if(c == 'a'){
                        return true;
                    }else{
                        state = 0;
                    };
                    break;
        }
        symbol++;
    }

    return false;
}

这可以用一个 for 循环更容易地编写，但是 while/switch 构造是必需的。

Answer 2

以下代码与您的实现类似，但它考虑了动态序列（不同的序列），并且不会混淆子字符串，而是迭代字符串的底层字符数组。

它还说明了从另一个序列开始的序列，例如：在字符串 "ABABAB" 中查找序列 "ABAB" 会在索引 0 处找到结果 "ABAB"和 "ABAB" 在索引 2 处找到。这可以通过注释掉 wIndex = startIndex.

轻松删除

代码：

public static void main (String[] args) throws java.lang.Exception {
    // Scanner input = new Scanner(System.in);
    String word = "B BABBABBA B";
    String seq = "ABBA";
    char[] wChars = word.toCharArray();
    char[] sChars = seq.toCharArray();
    int wIndex = 0; // wChars index
    int sIndex = 0; // sChars index
    int startIndex = 0; // starting index of the seq found in wChars

    System.out.println("Starting to evaluate...");

    while(wIndex < wChars.length) {
        if(wChars[wIndex] == sChars[sIndex]) {
            if(sIndex == 0) {
                startIndex = wIndex;
            }
            sIndex += 1;
        } else {
            sIndex = 0;
        }

        if(sIndex >= sChars.length) {
            System.out.println("Sequence \"" + seq + "\" found at index " + startIndex + ".");
            sIndex = 0;
            wIndex = startIndex; // set wIndex to startIndex to account for
                                 // sequence within a sequence, basically
                                 // backtracking
        }

        wIndex += 1;
    }
}

输出：

Starting to evaluate...
Sequence "ABBA" found at index 3.
Sequence "ABBA" found at index 6.

要搜索的有限状态机 "ABBA"

Finite State Machine to Search for "ABBA"

java

fsm