文字列検索のプログラムで2つのwhile文でやっていることを解説して頂けませんか？

Question

###前提・実現したいこと

文字列検索のプログラムで出現位置を出力するものです。
文字列Sから文字列Pを探して出現位置を出力するものです。

while文でやっていることを解説して頂きたいです。
1つ目や2つ目ののwhile文について解説して欲しいです。
やっていることを理解したいのでお願い致します。

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

エラーメッセージ

###該当のソースコード

import java.io.*;
import java.util.*;

public class Algo49{
	private static FastScanner sc = new FastScanner();

	public static void main(String[] args){
		char[] S = sc.next().toCharArray();
		char[] P = sc.next().toCharArray();
		int n = S.length;
		int m = P.length;

		int[] T = new int[m+1];
		T[0] = -1;
		T[1] = 0;
		int i = 2;
		int j = 0;
		while(i <= m){
			if(P[i-1] == P[j]){
				T[i] = j + 1;
				i++;
				j++;
			}else if(j > 0){
				j = T[j];
			}else{
				T[i] = 0;
				i++;
			}
		}

		i = 0;
		j = 0;
		StringBuilder ans = new StringBuilder();
		while(i + j < n){
			if(P[j] == S[i + j]){
				j++;
				if(j == m){
					ans.append(i);
					ans.append("\n");
				}else{
					continue;
				}
			}
			i = i + j - T[j];
			if(j > 0){
				j = T[j];
			}
		}

		System.out.print(ans);
	}

	static class FastScanner{
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(){
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next(){
			while(st == null || !st.hasMoreElements()){
				try{
					st = new StringTokenizer(br.readLine());
				}catch(IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt(){
			return Integer.parseInt(next());
		}

		long nextLong(){
			return Long.parseLong(next());
		}

		double nextDouble(){
			return Double.parseDouble(next());
		}

		String nextLine(){
			String str = "";
			try{
				str = br.readLine();
			}catch(IOException e){
				e.printStackTrace();
			}
			return str;
		}
	}
}

###試したこと
これは他人が書いたプログラムです。
短くまとまっているので参考にしようとしていますが、while文ブロックでの処理が何が行われているか、知りたいのです。

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

Comments

[m.ts10806]

自身がどこまで理解していてどこが分からないかを明確にしたほうが良いかと。

[s.t.]

このプログラムを書いた人に、変数の名前のつけかたを変えてもらうとわかりやすくなるかもしれません・・・。

[mattn]

「課題に対してアプローチしたことを記載してください」これはご自分で書く物です。

[kunai]

ダメなコードの書き方のお手本のようなコードですね。。

Answer 1

こういうものをアルゴリズムの初歩の勉強の教材として参考にするのはよいと思います。ただ、コードを読むことに慣れてない段階では字面を眺めても何をしているのか見えてこないと思います。

もしあなたが配列やJavaの++演算子の意味がわからないというレベルでしたら、プログラマー(のためのＱ＆Ａ)サイトで質問するのは遠慮した方がよさそうです。言語の基本知識を学ぶ前の段階の人はプログラマーとしての質問をすることは難しいということだと思います。

さて、Javaの文法や意味についてならわかるというのであれば、あなたに不足しているのはアルゴリズムを読み解く力ということになります。こちらの方もプログラマーが初期のころ自らの訓練によって身に着けるものなので、あまり初歩的なものだとやはりプログラマーのＱ＆Ａサイトで聞くのは少々はばかられると思った方がよいでしょう。

まぁしかしちょっとしたコツをご紹介しましょう。SとPは文字の配列ですね、Tはintの配列です。iとかjはこれらの配列の要素の位置を表すインデックスです。このwhile文で何をしているかを考えるには紙にペンで配列の絵とi,jがどこを指しているかを書き示し、自分が計算機になったつもりでどういうふうに値が変化していくかをシミュレートしてみるとよいと思います。

S +-+-+-+-+-+-+-+  i = 0
  |A|B|B|D|B|B|D|  j = 0
  +-+-+-+-+-+-+-+
P +-+-+-+
  |B|B|D|
  +-+-+-+
T +-+-+-+-+
  |0|0|0|0|
  +-+-+-+-+
最初のwhileループではどうなるか・・・

「うへぇ」と思ったかも知れませんが、このくらいのことはある程度の訓練を積んだプログラマーなら紙の上に一々書かなくても「頭の中にイメージを思い浮かべること」を普通にやっています。慣れてくるとこんなイメージさえ必要とせずコードから直接意味を読み取ることができるようになります。まぁしかし最初からは無理ですのでまずは紙とペンで地道にやってみてください。

Comments

[gyro16]

分かりました。

Answer 2

こちらの実装だと思いますので、全容わかるとイメージがより掴みやすいかと。

変数名わかりにくっ！と、私も思ったのですが意味あったのですね。

Comments

[momon-ga]

文字切れしてる・・・例のあれですね。
> 私も思ったのですが意味あったのですね。
と書いてあります。

[gyro16]

そうですね。これですね。