###前提・実現したいこと
for(compLen =1; compLen < idx.size() * 2; compLen *= 2){ Collections.sort(idx, new strIndexComp());
ここで行われている処理が追えません。
変数compLenが1から流れていって、sortしている様子が分かりません。
compare()が使われている様子が分かりません。
compareが明示的に使われていないので、なおさら分かりにくいです。
このプログラムは文字列t に、q個の与えられる文字列が含まれているかを判定するもので、
含まれていれば 1、含まれていなければ 0を表示するものです。
###発生している問題・エラーメッセージ
エラーメッセージ
###該当のソースコード
java
1 2import java.util.*; 3 4public class Algo51{ 5 public static void main(String[] args){ 6 7 Scanner scan = new Scanner(System.in); 8 String t = scan.next(); 9 StringIndex si = new StringIndex(t, false); 10 11 int q = scan.nextInt(); 12 for(int i = 0; i < q; i++) 13 if(si.isExist(scan.next(), t)) 14 System.out.println("1"); 15 else 16 System.out.println("0"); 17 18 scan.close(); 19 System.exit(0); 20 } 21} 22 23class StringIndex{ 24 class StIdx{ 25 int pos; 26 char ch; 27 28 public StIdx(int i, char c){ 29 pos = i; 30 ch = c; 31 } 32 } 33 34 List<StIdx> idx = new ArrayList<StIdx>(); 35 int[] seq; 36 int compLen = 1; 37 boolean debug; 38 39 public StringIndex(String t, boolean d){ 40 debug = d; 41 42 seq = new int[t.length()]; 43 for(int i = 0; i < t.length(); i++) 44 idx.add(new StIdx(i, t.charAt(i))); 45 46 for(compLen =1; compLen < idx.size() * 2; compLen *= 2){ 47 Collections.sort(idx, new strIndexComp()); 48 49 int[] tmp = new int[seq.length]; 50 51 tmp[idx.get(0).pos] = 1; 52 for(int i = 1; i < tmp.length; i++) 53 if(idxComp(idx.get(i-1), idx.get(i)) == 0) 54 tmp[idx.get(i).pos] = tmp[idx.get(i-1).pos]; 55 else 56 tmp[idx.get(i).pos] = tmp[idx.get(i-1).pos] + 1; 57 58 for(int i = 0; i < seq.length; i++) 59 seq[i] = tmp[i]; 60 61 if(debug){ 62 System.out.println("------------"); 63 for(int i = 0; i < idx.size(); i++) 64 System.out.println(i + "\t" + seq[idx.get(i).pos] + "\t" + idx.get(i).pos + "\t" 65 + t.substring(idx.get(i).pos)); 66 } 67 } 68 } 69 70 class strIndexComp implements Comparator<StIdx>{ 71 72 @Override 73 public int compare(StIdx o1, StIdx o2){ 74 return idxComp(o1, o2); 75 } 76 } 77 78 private int idxComp(StIdx o1, StIdx o2){ 79 if(compLen == 1) 80 if(o1.ch > o2.ch) 81 return 1; 82 else if(o1.ch == o2.ch) 83 return 0; 84 else 85 return -1; 86 87 if(seq[o1.pos] > seq[o2.pos]) 88 return 1; 89 if(seq[o1.pos] == seq[o2.pos]){ 90 int npos1 = o1.pos + compLen / 2; 91 int npos2 = o2.pos + compLen / 2; 92 int nseq1 = 0, nseq2 = 0; 93 if(npos1 < seq.length) 94 nseq1 = seq[npos1]; 95 if(npos2 < seq.length) 96 nseq2 = seq[npos2]; 97 if(nseq1 > nseq2) 98 return 1; 99 else if(nseq1 == nseq2) 100 return 0; 101 else 102 return -1; 103 } 104 return -1; 105 } 106 107 public boolean isExist(String p, String t){ 108 int low = 0, hi = idx.size() - 1; 109 return (findBin(p, t, low, hi)); 110 } 111 112 private boolean findBin(String p, String t, int low, int hi){ 113 if(low > hi) 114 return false; 115 int i = low + (hi - low) / 2; 116 int len = p.length(); 117 if(len > t.length() - idx.get(i).pos) 118 len = t.length() - idx.get(i).pos; 119 120 int r = p.substring(0, len).compareTo(t.substring(idx.get(i).pos, idx.get(i).pos + len)); 121 if(r == 0) 122 if(len == p.length()) 123 return true; 124 else 125 return findBin(p, t, i+1, hi); 126 else if(r < 0) 127 return findBin(p, t, low, i-1); 128 else 129 return findBin(p, t, i+1, hi); 130 } 131}
###試したこと
課題に対してアプローチしたことを記載してください
###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報
回答1件
あなたの回答
tips
プレビュー