Results 1 to 6 of 6
  1. #1
    XAW
    XAW is offline Member
    Join Date
    Apr 2012
    Posts
    3
    Rep Power
    0

    Default 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;
    import java.io.InputStreamReader;
    
    class Main {
    
        public static void main (String[] args) throws IOException {
    		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    		int cases=0;
    		int cases2=0;
    		String slowo=" ";
    		String word=" ";
    		int p=0;
    		cases=Integer.parseInt(br.readLine());
    		for(int i=0; i<cases; i++) {
    			if(slowo!=null && slowo.length()>0) {
    			slowo=br.readLine();
    			p=slowo.indexOf(" ");
    			cases2=Integer.parseInt(slowo.substring(0,p));
    			word=slowo.substring(p+1);
    			for(int k=0; k<cases2; k++) {
    			slowo=br.readLine();
    			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. #2
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,642
    Rep Power
    7

    Default 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. #3
    XAW
    XAW is offline Member
    Join Date
    Apr 2012
    Posts
    3
    Rep Power
    0

    Default 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. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,437
    Blog Entries
    7
    Rep Power
    20

    Default 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
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    XAW
    XAW is offline Member
    Join Date
    Apr 2012
    Posts
    3
    Rep Power
    0

    Default 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. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default Re: Need help to speed up algorithm

    If you don't understand my response, don't ignore it, ask a question.

Similar Threads

  1. Java Applet speed?
    By Masherbrum in forum New To Java
    Replies: 0
    Last Post: 04-06-2012, 03:11 AM
  2. Set max upload speed
    By Giuseppe_Mazzei in forum New To Java
    Replies: 9
    Last Post: 06-03-2011, 02:28 AM
  3. Improve the Speed of loop
    By venk123 in forum New To Java
    Replies: 15
    Last Post: 02-16-2011, 06:36 AM
  4. How to speed sql Statements?
    By bezudar in forum Advanced Java
    Replies: 3
    Last Post: 11-20-2008, 09:53 AM
  5. compare speed
    By bbq in forum JDBC
    Replies: 1
    Last Post: 06-28-2007, 05:34 PM

Posting Permissions

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