Algorithm to find minimum length in main string to find second string -


this question has answer here:

there 1 question of algorithm.

question follows:-

you given protein string consisting of characters, a, b, c, d. have find minimum length sequence in that.

example

0 1 2 3 4 5 6 7 8 9 10 11 12 b c d c b c d  c  c  d    string find : bcd   string find between (startpoint, endpoint) 1, 4 7, 9 1, 12 7, 12  minimum length of 7, 9.  answer 7, 9

my work,

  1. we can solve using brute force approach in o(n^2).
  2. we can find first sequence present in main string using dp, , dp logic follows, 
a = main string b = string find dp = dynamic programming function  n = a.size, m = b.size  build array of  dp[m+1][n+1]  dp[i][j], means if in a[0...i], b[0...j] present or not.  way can find our first occurence of b in a. after this, stuck.

i need hint side.

please give me hint/guidance only, no code or implementation required.

your sample problem , solution suggests solution numeric pair containing position of first letter of substring , position of last letter of substring i.e.

if substring bcd, solution position of b, position of d

provided rest of substring (c in case) falls in between solution pair.

so, give hint, can start finding positions of first letter of substring in main string , store positions in array. can find positions of last letter of substring , store them in array. give set of probable solution set wherein each pair comprise of 1 number array 1 , 1 number array 2 such number array 2 greater number array 1. might end observing there no such pair, means there no solution i.e. substring not exist in main string, or might end find 1 or more such pairs, means there can solution. left find out if rest of substring exists between solution pairs or not. if there more 1 such pairs found @ end, higher number minus lower number should resolve right solution. hope helps, mentioned not wish know entire answer, looking hint :)


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