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

Question

アルゴリズムの勉強をしています。
他の方が書いたプログラムを見ているのですが、わからない部分があります。

問題は、「リング状の文字列 s の任意の位置から、時計回りに連続した文字をいくつか選んで、文字列 p が作れるかを判定するプログラムを作成してください。」というものです。

例えば、
文字列s: vanceknowledgetoadと入力して
文字列p: advanceという文字列ができていれば、Yesを返すといった具合です。

import java.io.*;
 
class Main {
    public static void main(String[] args) {
        BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
        try {
            String s = kb.readLine();
            String p = kb.readLine();
             
            int slen = s.length();
            int plen = p.length();
            int j = 0;
            for( int i = 0; i<slen; i++ ) {
                if( p.charAt( 0 ) == s.charAt( i ) ) {
                    int ij = i;
                    for( j = 0; j<plen; j++ ) {
                        ij = ( i+j ) % slen;
                        if( p.charAt( j ) != s.charAt( ij ) ) {
                            break;
                        }
                    }
                }
                if( plen == j ) { break; }
            }
             
            if( plen == j ) {
                System.out.println( "Yes" );            
            } else {
                System.out.println( "No" );
            }
        } catch( IOException e ) {
            System.err.println( e );
        }
    }
}

最初のif (p.charAr(0) == s.charAr(i)の部分は、文字列pの最初の文字と文字列sが合うかを判定しているとわかります。
その後のfor以下がよくわかりません。
一番わからないのは、ij = (i+j) % slenの部分です。
なぜ、i+jをslenで割った余りを求めているのでしょうか？

        for( int i = 0; i<slen; i++ ) {
            if( p.charAt( 0 ) == s.charAt( i ) ) {
                int ij = i;
                for( j = 0; j<plen; j++ ) {
                    ij = ( i+j ) % slen;
                    if( p.charAt( j ) != s.charAt( ij ) ) {
                        break;
                    }
                }
            }
            if( plen == j ) { break; }

考えているのですが、どうしてかよくわかりません。
ご回答頂けますと助かります。
よろしくお願い致します。

Answer 1

余りを使うことでリング状の文字列をループさせています。

n    : 0 1 2 3 4 5 6 7 8 9 ...
n % 3: 0 1 2 0 1 2 0 1 2 0 ... 

Comments

[退会済みユーザー]

回答ありがとうございます。

文字列をループさせるために、余りを出しているのですね。

ありがとうございました。

Answer 2

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

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

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

Comments

[退会済みユーザー]

回答ありがとうございます。

詳しく説明して頂けたので、理解できたような気がします。

この手の処理ではよく使われるとの事、しっかり覚えたいと思います。

ありがとうございました。

Answer 3

i: 0 1 2 3 4 5 6
s: A B C D E F G
   |
j: 0 1 2 3 4
p: X X X X X

i: 0 1 2 3 4 5 6
s: A B C D E F G
     |
  j: 0 1 2 3 4
  p: X X X X X

こんな感じで一つずつ比較の開始位置をずらして一致するか見ていこうって方針なわけですが、

例えばその過程で

i: 0 1 2 3 4 5 6
s: A B C D E F G
             |
          j: 0 1 2 3 4
          p: X X X X X

こういうずれ方のとき(i=5)

jと比較すべき添字をijとすると

j	ij
0	5
1	6
2	0
3	1
4	2

すなわちij=(5+j)%6 = (i+j)%slen

Comments

[退会済みユーザー]

回答ありがとうございます。

詳しい説明をして頂いたので、わかった気がします。

もう一つお聞きしたいのですが、ループさせているということは、if( p.charAt( j ) != s.charAt( ij ) )の部分は、p.charAt(0)の頭文字以降があっているか判定している で良いでしょうか？

[ozwk]

そうですね

[退会済みユーザー]

ありがとうございます。
しっかり理解できました。