# Thread: Need help to speed up algorithm

1. Member
Join Date
Apr 2012
Posts
3
Rep Power
0

## Need help to speed up algorithm

Hi. I'm trying to do Sphere Online Judge (SPOJ) - Problem DICTSUB

But I'm getting timeout..So i need to speed up my algorithm. How improve my code or write new better code?

Java Code:
```import java.io.BufferedReader;
import java.io.IOException;

class Main {

public static void main (String[] args) throws IOException {
int cases=0;
int cases2=0;
String slowo=" ";
String word=" ";
int p=0;
for(int i=0; i<cases; i++) {
if(slowo!=null && slowo.length()>0) {
p=slowo.indexOf(" ");
cases2=Integer.parseInt(slowo.substring(0,p));
word=slowo.substring(p+1);
for(int k=0; k<cases2; k++) {
slowo=decode(slowo);
int pom=0;
int x=0;
while(pom!=-1 && x<slowo.length()) {
pom=word.indexOf(slowo.charAt(x),pom);
x++;
}
if(pom!=-1) System.out.println("YES");
else System.out.println("NO");

}
}
System.out.print("\r");
}
}

public static String decode(String W) {
char[] array=W.toCharArray();
StringBuilder ret=new StringBuilder("");
int pom=0;
for(int i=0; i<array.length; i++)
if(i%2==0) pom=array[i];
else for(int k=0; k<pom; k++) ret.append(array[i]);
return ret.toString();
}

}```

2. Moderator
Join Date
Jul 2010
Location
California
Posts
1,641
Rep Power
9

## Re: Need help to speed up algorithm

First, you should define what you mean by 'timeout'. Second, if you wish to speed this up, I recommend profiling your code by timing operations using System.currentTimeMillis - only then will you know which part of your algorithm is the bottleneck so you can focus on that.

3. Member
Join Date
Apr 2012
Posts
3
Rep Power
0

## Re: Need help to speed up algorithm

SPOJ has time limit for each task. Your code has some time to be performed. We don't know what input author prepared for our algorithm.

The slowest part of my code is comparing strings:

Java Code:
```
while(pom!=-1 && x<slowo.length()) {
pom=word.indexOf(slowo.charAt(x),pom);
x++;
}```
I need faster method to compare strings. But how to do that?
Last edited by Norm; 04-07-2012 at 02:03 AM. Reason: fixed code tags

4. ## Re: Need help to speed up algorithm

How, exactly, is a String from the dictionary encoded? You assume an RLE as <len><char><len><char> ... is the <len> a binary encoded number or do you have to read its character representation?

kind regards,

Jos

5. Member
Join Date
Apr 2012
Posts
3
Rep Power
0

## Re: Need help to speed up algorithm

I could encode "normal" Strings to RLE and then compare but I tried this and it was still too slow..Or did you mean something else?

6. ## Re: Need help to speed up algorithm

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•