Witam. Napisałem algorytm (zadanie na SPOJ-a: http://pl.spoj.pl/problems/WORDBASE/ ), jednak otrzymuję w testach albo błędne odpowiedzi, albo przekroczony limit czasu, albo nawet błąd wykonania. Byłbym wdzięczny za pomoc w znalezieniu błędów w moim kodzie (czy też po prostu wprowadzeniu optymalizacji w nim):
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
static PrintWriter out=new PrintWriter(new BufferedOutputStream(System.out));
String[] slownik=new String[1000001];
int slow=0;
String lastWord=null;
Sortowanie sort = new Sortowanie();
void add(String word) {
if(!zawiera(word)) {
slownik[slow]=word;
slow++;
lastWord=word;
Arrays.sort(slownik, 0, slow, sort);
}
}
void addSuffix(String word, int prefix) {
if(prefix<=lastWord.length()) {
String slowo=lastWord.substring(0,prefix)+word;
add(slowo);
}
}
void delete(String word) {
int pozycja=Arrays.binarySearch(slownik, 0, slow, word, sort);
if(pozycja>=0)
{
slownik[pozycja]=null;
for(int i=pozycja; i<slow-1; i++) slownik[i]=slownik[i+1];
slownik[slow-1]=null;
slow--;
}
}
void count(String word1, String word2) {
int porownanie=sort.compare(word1, word2);
if(porownanie==0) {
if(zawiera(word1)) out.println(1);
else out.println(0);
}
else if(porownanie<0) {
int pozycja=Arrays.binarySearch(slownik, 0, slow, word1, sort);
int pozycja2=Arrays.binarySearch(slownik, 0, slow, word2, sort);
if(pozycja>=0 && pozycja2>=0) out.println(pozycja2-pozycja+1);
else if(pozycja<0 && pozycja2>=0) {
pozycja=Math.abs(pozycja+1);
out.println(pozycja2-pozycja+1);
}
else if(pozycja>=0 && pozycja2<0) {
pozycja2=Math.abs(pozycja2+1);
out.println(pozycja2-pozycja);
}
else {
pozycja=Math.abs(pozycja+1);
pozycja2=Math.abs(pozycja2+1);
out.println(pozycja2-pozycja);
}
}
else { //word1>word2
int pozycja=Arrays.binarySearch(slownik, 0, slow, word1, sort);
int pozycja2=Arrays.binarySearch(slownik, 0, slow, word2, sort);
if(pozycja>=0 && pozycja2>=0) out.println(pozycja-pozycja2+1);
else if(pozycja<0 && pozycja2>=0) {
pozycja=Math.abs(pozycja+1);
out.println(pozycja-pozycja2+1);
}
else if(pozycja>=0 && pozycja2<0) {
pozycja2=Math.abs(pozycja2+1);
out.println(pozycja-pozycja2+1);
}
else {
pozycja=Math.abs(pozycja+1);
pozycja2=Math.abs(pozycja2+1);
out.println(pozycja-pozycja2);
}
}
}
void list(String word1, String word2) {
int porownanie=sort.compare(word1, word2);
if(porownanie==0) {
if(zawiera(word1)) out.println(word1);
}
else if(porownanie<0) {
int pozycja=Arrays.binarySearch(slownik, 0, slow, word1, sort);
pozycja=Math.abs(pozycja+1);
int pozycja2=Arrays.binarySearch(slownik, 0, slow, word2, sort);
pozycja2=Math.abs(pozycja2+1);
if(pozycja2==slow) pozycja2--;
while(pozycja<=pozycja2) {
out.println(slownik[pozycja]);
pozycja++;
}
}
else {
int pozycja=Arrays.binarySearch(slownik, 0, slow, word2, sort);
pozycja=Math.abs(pozycja+1);
int pozycja2=Arrays.binarySearch(slownik, 0, slow, word1, sort);
pozycja2=Math.abs(pozycja2+1);
if(pozycja2==slow) pozycja2--;
while(pozycja2>=pozycja) {
out.println(slownik[pozycja2]);
pozycja2--;
}
}
}
void show(int n) {
if(n<=slow) out.println(slownik[n-1]);
}
boolean zawiera(String word) {
if(slow==0) return false;
return Arrays.binarySearch(slownik, 0, slow, word, sort)>=0?true:false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Main dict=new Main();
int t=Integer.parseInt(br.readLine());
String slowo="";
for(int i=0; i<t; i++) {
slowo=br.readLine();
if(slowo.contains("add [")) {
int p1=slowo.indexOf("[");
int p2=slowo.indexOf("]");
int p3=slowo.indexOf(" ",p2);
dict.addSuffix(slowo.substring(p3+1),Integer.parseInt(slowo.substring(p1+1,p2)));
}
else if(slowo.contains("add") && !slowo.contains("add [")) dict.add(slowo.substring(slowo.indexOf(" ")+1));
else if(slowo.contains("delete")) dict.delete(slowo.substring(slowo.indexOf(" ")+1));
else if(slowo.contains("count")) {
int p1=slowo.indexOf(" ");
int p2=slowo.indexOf(" ",p1+1);
String w1=slowo.substring(p1+1,p2);
String w2=slowo.substring(p2+1);
dict.count(w1, w2);
}
else if(slowo.contains("list")) {
int p1=slowo.indexOf(" ");
int p2=slowo.indexOf(" ",p1+1);
String w1=slowo.substring(p1+1,p2);
String w2=slowo.substring(p2+1);
dict.list(w1, w2);
}
else if(slowo.contains("show")) dict.show(Integer.parseInt(slowo.substring(slowo.indexOf(" ")+1)));
}
out.flush();
}
static class Sortowanie implements Comparator<String> {
public int compare(String s1, String s2) {
if(s1==null && s2!=null) return 1;
else if(s1!=null && s2==null) return -1;
else if(s1==null && s2==null) return 0;
else if(s1.equals(s2)) return 0;
else if(s1.charAt(0)==s2.charAt(0)) {
if(s1.length()==1) return -1;
else if(s2.length()==1) return 1;
else return compare(s1.substring(1,s1.length()),s2.substring(1,s2.length()));
}
else if(s1.charAt(0)=='c') return -1;
else if(s2.charAt(0)=='c') return 1;
else if(s1.charAt(0)=='g') return -1;
else if(s2.charAt(0)=='g') return 1;
else if(s1.charAt(0)=='t') return -1;
else return 1; //gdy s2.charAt(0)=='t'
}
}
}