Алгоритм касаи

Алгоритм касаи

Алгоритм Касаи — алгоритм, который ищет самый длинный общий префикс из поданных на вход в лексиграфическом порядке массиве префиксов некоторой строки. (LCP — Longest Common Prefix)

Реализация алгоритма на языке Java.

import java.io.*;
import java.util.*;
import java.math.*;
 
public class Task {
 
	public static void main(String[] args) throws FileNotFoundException {
		Scanner InF = new Scanner(new File(«input.txt»));
		PrintWriter OutF = new PrintWriter(«output.txt»);
		String A = InF.nextLine(), P[] = new String[A.length()+1];
		for (int i = 0; i < A.length(); i++) {
			P[i+1] = A.substring(i);
		}
		P[0] = "";
		Arrays.sort(P);
		int Pos[] = new int[A.length()+1];
		for (int i = 1; i <= A.length(); i++) {
			Pos[i] = A.length() - P[i].length() + 1;
		}<br>
		int Rank[] = new int[A.length()+1];
		for (int i = 1; i <= A.length(); i++) {
			Rank[Pos[i]] = i;
		}<br>
		int H8[] = new int[A.length()+1];
		int h = 0;
		for (int i = 1; i <= A.length(); i++) {
			if (Rank[i] > 1) {
				int k = Pos[Rank[i]-1];
				while (((i+h-1)!=A.length())
						&&((k+h-1)!=A.length())
						&&(A.charAt(i+h-1) == A.charAt(k+h-1)))
					h++;
				H8[Rank[i]] = h;
				if (h > 0)
					h--;
			}
		}
		for (int i = 0; i <= A.length(); i++) {
			OutF.print(P[i]);
			OutF.print(" ");
			OutF.println(H8[i]);
		}
 
		InF.close();
		OutF.close();
	}
}

Связать^?