Java リング状の文字列の任意の位置から抽出した文字列との比較

何のこっちゃ？という分かりにくいタイトルですが、AIZU ONLINE JUDGEの問題で出てきまして、入力自体は1行の文字列ではあるけれど、リング状になっていると考えて、どこから数え始めても良いと。

で、もう1つの入力値の文字列が作れるかどうかを判定すると。

⇧  「入力値１」をリング状にして、任意の位置から切り出した文字列で、「入力値２」が表現できるかどうかですかね。この場合は、Yes。

で、「入力値１」が変わらず、「入力値２」が、advanced とかになると、No。

というような判定をプログラミングすると。

 

そして、全然関係ないけど、

simplearchitect.hatenablog.com

simplearchitect.hatenablog.com

⇧  やはり、合衆国はスゴイらしいですね...ディスカッションが楽しいって感覚とか持てるようになりたいですね。

ということで、今回は、Javaです。

そんでは、レッツ～トライ。

 

考え方

どう実装すれば良いのかしら？

teratail.com

文字列sはリング状のものとして扱ってはいますが、
プログラム上はただの文字列(配列)です。

目的の文字頭が後ろにあった場合、
そのインデックスを基点に+1,+2,+3...と調べていくと
配列の長さを超えてしまう場合があります。
そこに無理やりアクセスしようとするとIndexOutOfBoundsとなるだけなので
インデックスが配列の長さと同じになった場合は、
インデックスを配列の長さ分引いて、配列の頭に戻す必要があります。

インデックスを配列の長さで割った余りを求める、というのは、
上のような処理を1行で書けるので、この手の処理ではよくつかわれています。

Java - リング状の文字列の判定 アルゴリズム わからない部分があります。｜teratail

⇧  teratail で上がってましたね。

マジっすか...よく使われるって...初めて知りましたわ（涙）

 

実際に実装してみる

どんな感じのソースになるかというと、 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class TestRing {

  public static void main(String[] args) {
    // TODO 自動生成されたメソッド・スタブ
    BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
    try {
      String ringStr = kb.readLine();    // リング状の文字列
      String targetStr = kb.readLine();  // 対象の文字列

      int ringStrLen = ringStr.length();     // リング状の文字列の長さ
      int targetStrLen = targetStr.length(); // 対象の文字列の長さ
      int j = 0;
      for( int i = 0; i < ringStrLen; i++ ) {
        if( targetStr.charAt( 0 ) == ringStr.charAt( i ) ) {
          // リング状の文字列における対象の文字列のインデックス用
          int ij = i;
          for( j = 0; j < targetStrLen; j++ ) {
            // リング状の文字列のインデックスを超えないように剰余演算
            ij = ( i+j ) % ringStrLen;
            // 文字が一致しない場合、リング状の文字列の次の文字に進めるため処理を抜ける
            if( targetStr.charAt( j ) != ringStr.charAt( ij ) ) {
              break;
            }
          }
        }
        // 対象の文字列が見つかった場合、処理を抜ける
        if( targetStrLen == j ) { break; }
      }

      // 対象の文字列が見つかった場合、j = 0 にリセットされないので、
      if( targetStrLen == j ) {
        System.out.println( "Yes" );            
      } else {
        System.out.println( "No" );
      }
    } catch( IOException e ) {
      System.err.println( e );
    }
  }
}

んで、実行。

リング状の文字列から作成できる場合

リング状の文字列から作成できない場合

 

teratail.com⇧  teratail の解説を参考にすると、

i = 16 で一致した文字で検証をスタートした場合、「ij = ( i+j ) % ringStrLen」って部分は、ringStrLen = 18 になる（「vanceknowledgetoad」なので、文字列の長さは18）のであるからして、

i	j	ij = ( i+j ) % ringStrLen
16	0	16
16	1	17
16	2	0
16	3	1
16	4	2
16	5	3
16	6	4

ってことになるらしい。

う～ん、上手いこと、リング状の文字列の最初のほうの文字を参照するようになってますね。なんか、あんまり理解はできないんだけど、こういうロジックもあるんだということで。

今回はこのへんで。