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

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

Реализация алгоритма на языке Java. <source lang="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; }
int Rank[] = new int[A.length()+1]; for (int i = 1; i <= A.length(); i++) { Rank[Pos[i]] = i; }
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(); } } </source>