JavaでSuffixArray
書いてしまったので一応載せておきます。勉強用のコードなので入力文字列が巨大になったときにどういう挙動を示すかは考えていません。
import java.util.Iterator;
import java.util.Vector;
public class Test {
static char[] buffer;
public static void main(String[] args) {
String input = "abracadabra$";
Vector<Integer> vec = new Vector<Integer>(input.length());
for(int i = 0; i < input.length() - 1; i++){
vec.add(i);
}
buffer = input.toCharArray();
vec = sort(vec);
for (Iterator<Integer> iter = vec.iterator(); iter.hasNext();) {
Integer i = iter.next();
System.out.println(input.substring(i));
}
}
static boolean compare(Integer i, Integer j){
int w = 0;
while(true){
if(buffer[i + w] < buffer[j + w]){
return true;
}else if(buffer[i + w] > buffer[j + w]){
return false;
}
w++;
}
}
static Vector<Integer> sort(Vector<Integer> vec) {
if(vec.size() < 2){
return vec;
}
Integer pivot = vec.get(0);
Vector<Integer> less = new Vector<Integer>();
Vector<Integer> more = new Vector<Integer>();
for(int i = 1; i < vec.size(); i++){
Integer v = vec.get(i);
if(compare(v, pivot)){
less.add(v);
}else{
more.add(v);
}
}
Vector<Integer> result;
result = sort(less);
result.add(pivot);
result.addAll(sort(more));
return result;
}
}
