質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.35%

  • Java

    14374questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

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

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 418

szk24

score 70

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

問題は、「リング状の文字列 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; }

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+2

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/28 12:03

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

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

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

    キャンセル

checkベストアンサー

+1

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/28 12:09

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

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

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

    キャンセル

  • 2017/09/28 12:11

    そうですね

    キャンセル

  • 2017/09/28 12:12

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

    キャンセル

+1

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/09/28 12:11

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

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

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

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.35%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • Java

    14374questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。