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

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

ただいまの
回答率

90.51%

  • Java

    15831questions

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

sortが行われている様子が分かりません。どのように処理が流れているのでしょうか?

解決済

回答 1

投稿 編集

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

gyro16

score 77

前提・実現したいこと

for(compLen =1; compLen < idx.size() * 2; compLen *= 2){
Collections.sort(idx, new strIndexComp());

ここで行われている処理が追えません。
変数compLenが1から流れていって、sortしている様子が分かりません。

compare()が使われている様子が分かりません。
compareが明示的に使われていないので、なおさら分かりにくいです。

このプログラムは文字列t に、q個の与えられる文字列が含まれているかを判定するもので、
含まれていれば 1、含まれていなければ 0を表示するものです。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

import java.util.*;

public class Algo51{
    public static void main(String[] args){

        Scanner scan = new Scanner(System.in);
        String t = scan.next();
        StringIndex si = new StringIndex(t, false);

        int q = scan.nextInt();
        for(int i = 0; i < q; i++)
            if(si.isExist(scan.next(), t))
                System.out.println("1");
            else
                System.out.println("0");

        scan.close();
        System.exit(0);
    }
}

class StringIndex{
    class StIdx{
        int pos;
        char ch;

        public StIdx(int i, char c){
            pos = i;
            ch = c;
        }
    }

    List<StIdx> idx = new ArrayList<StIdx>();
    int[] seq;
    int compLen = 1;
    boolean debug;

    public StringIndex(String t, boolean d){
        debug = d;

        seq = new int[t.length()];
        for(int i = 0; i < t.length(); i++)
            idx.add(new StIdx(i, t.charAt(i)));

        for(compLen =1; compLen < idx.size() * 2; compLen *= 2){
            Collections.sort(idx, new strIndexComp());

            int[] tmp = new int[seq.length];

            tmp[idx.get(0).pos] = 1;
            for(int i = 1; i < tmp.length; i++)
                if(idxComp(idx.get(i-1), idx.get(i)) == 0)
                    tmp[idx.get(i).pos] = tmp[idx.get(i-1).pos];
                else
                    tmp[idx.get(i).pos] = tmp[idx.get(i-1).pos] + 1;

            for(int i = 0; i < seq.length; i++)
                seq[i] = tmp[i];

            if(debug){
                System.out.println("------------");
                for(int i = 0; i < idx.size(); i++)
                    System.out.println(i + "\t" + seq[idx.get(i).pos] + "\t" + idx.get(i).pos + "\t"
                        + t.substring(idx.get(i).pos));
            }
        }
    }

    class strIndexComp implements Comparator<StIdx>{

        @Override
        public int compare(StIdx o1, StIdx o2){
            return idxComp(o1, o2);
        }
    }

    private int idxComp(StIdx o1, StIdx o2){
        if(compLen == 1)
            if(o1.ch > o2.ch)
                return 1;
            else if(o1.ch == o2.ch)
                return 0;
            else
                return -1;

            if(seq[o1.pos] > seq[o2.pos])
                return 1;
            if(seq[o1.pos] == seq[o2.pos]){
                int npos1 = o1.pos + compLen / 2;
                int npos2 = o2.pos + compLen / 2;
                int nseq1 = 0, nseq2 = 0;
                if(npos1 < seq.length)
                    nseq1 = seq[npos1];
                if(npos2 < seq.length)
                    nseq2 = seq[npos2];
                if(nseq1 > nseq2)
                    return 1;
                else if(nseq1 == nseq2)
                    return 0;
                else
                    return -1;
            }
            return -1;
    }

    public boolean isExist(String p, String t){
        int low = 0, hi = idx.size() - 1;
        return (findBin(p, t, low, hi));
    }

    private boolean findBin(String p, String t, int low, int hi){
        if(low > hi)
            return false;
        int i = low + (hi - low) / 2;
        int len = p.length();
        if(len > t.length() - idx.get(i).pos)
            len = t.length() - idx.get(i).pos;

        int r = p.substring(0, len).compareTo(t.substring(idx.get(i).pos, idx.get(i).pos + len));
        if(r == 0)
            if(len == p.length())
                return true;
            else
                return findBin(p, t, i+1, hi);
        else if(r < 0)
            return findBin(p, t, low, i-1);
        else
            return findBin(p, t, i+1, hi);
    }
}

試したこと

課題に対してアプローチしたことを記載してください

補足情報(言語/FW/ツール等のバージョンなど)

より詳細な情報

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • KSwordOfHaste

    2017/07/08 15:03 編集

    前半のコード(タグ```で囲まれていない部分)は後半のコードに含まれているようなので冗長ではないでしょうか?質問文にある不要な部分を整理した方がよいと思います。

    キャンセル

  • KSwordOfHaste

    2017/07/08 16:52

    質問したいポイントがStringIndexクラスの機能の方なのであれば確かに難しい機能だと思います。しかしsortとComparatorの関係については比較的単純です。疑問点はStringIndexクラスの機能の方でしょうか?それともsortとComparatorの関係でしょうか?

    キャンセル

  • gyro16

    2017/07/08 17:19

    Comparatorに従ってsortする感覚は分かりますが、Overrideされているcompareが明示的に使われていないのでどう回しているか分かりません。

    キャンセル

回答 1

checkベストアンサー

+1

コード上にstrIndexComp#compareの呼び出しは出てきませんが、それはsortメソッドの実装内部から呼び出されます。List#sortは内部でなんらかのアルゴリズム(Oracle提供のJavaの標準ライブラリーではマージソートを用いているようです)に従って要素を並べ替えますが、どのようなアルゴリズムで並べ替えるにせよ、要素ごとの比較をしなければならない場面が出てきます。その際にsort内部からstrIndexComp#compareが呼び出されます。

実際の実装とは違いますが例えばList#sortが選択ソートアルゴリズムで実装されていたときのコードのイメージを示してみますと以下のようになります。つまり、ソートの途中で必要な回数だけcompareが呼び出されるわけです。

public interface List<E> extends Collection<E> {
  default void sort(Comparator<? super E> c) {
    for (int i = 0; i < size() - 1; i++) {
      E min = get(i);
      int minIndex = i;
      for (int j = size(); --j > i; ) {
        E e = get(j);
        if (c.compare(min, e) > 0) { // <= このように呼び出される
          min = e;
          minIndex = j;
        }
      }
      if (minIndex != i) {
        set(minIndex, get(i));
        set(i, min);
      }
    }
  }
}

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/07/11 17:13

    ありがとうございました。チャートを追うことができました。

    キャンセル

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

  • Java

    15831questions

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