"ABBA"を検索する有限状態マシン

Question

私は文字列 "ABBA"が存在するかどうかを調べるために、AsおよびBsの文字列を検索する有限状態マシンのモデリングのためのwhileスイッチケースを作成しようとしています。私がちょうど "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; 
} 

これはただでより簡単に記述できます。ここ

は、状態図..です私は次の実装を提案してみましょうa 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.