java - 1772 of Caribbean online judge giving a time limit exceeded error. please help me find why is my algorithm taking so long -


so trying solve problem 1772 of caribbean online judge web page http://coj.uci.cu/24h/problem.xhtml?abb=1772, problem asks find if substring of bigger string contains @ least 1 palindrome inside it:

e.g. analyzing sub-strings taken following string: "baraabarbabartaarabcde"

"bara" contains palindrome "ara"

"abar" contains palindrome "aba"

"babar" contains palindrome "babar"

"taar" contains palindrome "aa"

"abcde" not contains palindrome.

etc etc etc...

i believe approach fast because iterating strings starting @ first char , @ last char @ same time, advancing towards center of string looking following patterns: "aa" "aba" whenever find pattern can substring given contains palindrome inside it. problem algorithm taking long time can't spot problem on it. please me find lost on one. here algorithm 

public static boolean haspalindromeinside(string str) {     int midpoint=(int) math.ceil((float)str.length()/2.0);     int k = str.length()-1;      for(int = 0; < midpoint;i++)     {         char letterleft = str.charat(i);         char secondletterleft=str.charat(i+1);         char letterright = str.charat(k);         char secondletterright =  str.charat(k-1);          if((i+2)<str.length())         {             char thirdletterleft=str.charat(i+2);             char thirdletterright=str.charat(k-2);               if(letterleft == thirdletterleft || letterright == thirdletterright)             {                 return true;             }          }           if(letterleft == secondletterleft || letterright==secondletterright)         {             return true;         }      k--;     }     return false; } }

i have removed code grabs input strings , intervals of sub-strings, using string.substring() substrings , don't think causing problem. if need code please let me know. thanks!

i think can solve in o(1) time per query given o(n) preprocessing find locations of 2 , 3 character palindromes. (any plaindrome have 2 character plaindrome @ centre, while odd have 3 character 1 suffices check 2 , 3.)

for example,

given string baraabarbabartaarabcde, first compute array indicating locations of 2 character palindromes:

baraabarbabartaarabcde 000100000000001000000-

then compute cumulative sum of array:

baraabarbabartaarabcde 000100000000001000000- 000111111111112222222-

by doing subtraction can work out whether there 2 character palindromes in query range.

similarly 3 character plaindromes:

baraabarbabartaarabcde  string 01001000100000010000--  indicator 01112222333333344444--  cumulative

Comments

Post a Comment

Popular posts from this blog

java.util.scanner - How to read and add only numbers to array from a text file -

i'm learning java , have question regarding reading file want read numbers file contains strings well. here example of file: 66.56 "3 java 3-43 5-42 2.1 1 and here coding: public class test { public static void main (string [] args){ if (0 < args.length) { file x = new file(args[0]); try{ scanner in = new scanner( new fileinputstream(x)); arraylist<double> test = new arraylist<>(); while(in.hasnext()){ if(in.hasnextdouble()){ double f=in.nextdouble(); test.add(f);} else {in.next();} } catch(ioexception e) { system.err.println("exception during reading: " + e); } } my problem add 66.56,2.1 , 1 doesn't add 3 after "3 or ignores 3-43 , 5-42 can tell me how skip strings , add doubles here? thanks all said 3 ie; "3, 3-43 , 4-42 strings either u read string , split , check number @ " , - or put in space between characters , integers. jvm after compilation tre...
Read more

rewrite - Trouble with Wordpress multiple custom querystrings -

i'm working on adding multiple querystring , doesn't seem work. i've found codes seems work others might i'm missing something. i want like: http://mydomain.com/board/?getyear=2013&getsometext2=sometext to http://mydomain.com/board/2013/sometext/ i added code below functions.php file. doesn't seem work should though. this works. echoing querystring gets both variable without problem. http://mydomain.com/board/2013/sometext/ but doesn't. tested querystring vis isset() seems nothing being set/get http://mydomain.com/board/2013/ function add_query_vars($vars) { $vars[] = "getyear"; $vars[] = "getsometext2"; return $vars; } add_filter('query_vars', 'add_query_vars'); function add_rewrite_rules($arules) { $anewrules = array('board/([^/]+)/([^/]+)/?$' => 'index.php?pagename=board&getyear=$matches[1]&getsometext2=$matches[2]'); $arules = $a...
Read more