Tym razem mam problem z takim zadaniem:
LCP
Pewnie już poznałeś problem Porządek sufiksów. Tym razem sortujemy sufiksy przyjmując, że na końcu łancucha znaków znajduje się unikatowy symbol największy w alfabecie. Na przykład dla słowa abaabaabbaababaabaa, porządek sufiksów jest nastepujacy:0 : (lcp= 5) : S_{ 2} : aabaabbaababaabaa
1 : (lcp= 4) : S_{14} : aabaa
2 : (lcp= 3) : S_{ 9} : aababaabaa
3 : (lcp= 2) : S_{ 5} : aabbaababaabaa
4 : (lcp= 1) : S_{17} : aa
5 : (lcp= 7) : S_{ 0} : abaabaabbaababaabaa
6 : (lcp= 5) : S_{12} : abaabaa
7 : (lcp= 4) : S_{ 3} : abaabbaababaabaa
8 : (lcp= 3) : S_{15} : abaa
9 : (lcp= 2) : S_{10} : ababaabaa
10 : (lcp= 1) : S_{ 6} : abbaababaabaa
11 : (lcp= 0) : S_{18} : a
12 : (lcp= 6) : S_{ 1} : baabaabbaababaabaa
13 : (lcp= 5) : S_{13} : baabaa
14 : (lcp= 4) : S_{ 8} : baababaabaa
15 : (lcp= 3) : S_{ 4} : baabbaababaabaa
16 : (lcp= 2) : S_{16} : baa
17 : (lcp= 1) : S_{11} : babaabaa
18 : : S_{ 7} : bbaababaabaaPewnie zauważyłeś, że wypisywane są pewne liczby lcp (longest common prefix) - długość najdłuższego wspólnego prefiksu z następnym w kolejności leksykograficznej sufiksem.
Twoim zadaniem jest wyznaczyć tablicę LCP
Specyfikacja wejścia
W pierwszym wierszu dana jest liczba n napisów (n < 20). W kolejnych wierszach dane są słowa złożone tylko z liter {a-z}. Każde słowo ma nie więcej niż 1000000 znaków.Przykładowe wejście
3
ababa
abc
abaabaabbaababaabaaWyjście
3 1 0 2
0 0
5 4 3 2 1 7 5 4 3 2 1 0 6 5 4 3 2 1
Napisałem algorytm, który działa idealnie dla przykładowych danych i nie wiem naprawdę nie wiem gdzie jest błąd (nie chce mi zaakceptować informując o przekroczeniu czasu więc może jest za wolny tylko jak go przyspieszyć?).
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
class Glowna {
static ArrayList<String> sufiksy = new ArrayList<String>();
private static class Sortowanie implements Comparator<String> {
public int compare(String s1, String s2) {
if(s1.length()==s2.length()) return s1.compareTo(s2);
else if(s1.length()<s2.length()) {
String pom2=s2.substring(0,s1.length());
if(s1.contains(pom2) && s1.length()==pom2.length()) return 1;
else return s1.compareTo(s2);
}
else if(s1.length()>s2.length()) {
String pom2=s1.substring(0,s2.length());
if(s2.contains(pom2) && s2.length()==pom2.length()) return -1;
else return s1.compareTo(s2);
}
else return 0;
}
}
public static void main(String[] args) throws IOException, NumberFormatException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
String slowo=" ";
for(int i=0; i<n && slowo!=null; i++) {
sufiksy.clear();
slowo=br.readLine();
if(slowo!=null) {
for(int k=0; k<slowo.length(); k++) sufiksy.add(slowo.substring(k));
Comparator<String> s = new Sortowanie();
Collections.sort(sufiksy, s);
for(int k=0; k<sufiksy.size()-1; k++)
if(k<sufiksy.size()-2) System.out.print(LCP(k)+" ");
else System.out.print(LCP(k));
System.out.println();
}
}
}
private static int LCP(int k) {
String slowo1=sufiksy.get(k);
String slowo2=sufiksy.get(k+1);
char[] s1=slowo1.toCharArray();
char[] s2=slowo2.toCharArray();
int i=0;
while(i<slowo2.length() && i<slowo1.length() && s1[i]==s2[i]) i++;
return i;
}
}
Z góry dzięki za podpowiedzi!