search
Log In
0 votes
177 views
Given a text array $T[1…..n]$ and a pattern array $P[1….m]$ such that T and P are character taken from alphabet $\sum$,

$\sum={a,b,c,…..z}$. String matching problem is to find all the occurence of P in T. A pattern occur with shift s in T if $P[1…..m]=T[s+1,…...s+m]$.

Consider $T=bacacbaacacac$

               $P=cac$

The sum of the value of all s is ________
in Algorithms
edited by
177 views

2 Answers

2 votes
 
Best answer

The 3 occurrences of "cac"  are as shown: 

bacacbaacacac

bacacbaacacac

bacacbaacacac 

For the first occurrence, 

P[1..3]= cac = T[3..5]. 

Now s+1=3, thus s=2.

Calculating s for the other 2 occurrences, we get s= 8 and s=10. So sum of all values of s is 20.


selected by
1 vote

s =2 + 8 + 10 = 20

0

Could you please elaborate? I am not getting this part of the question:"A pattern occur with shift s in T if P[1…..m]=T[s+1,…...s+m]". Got the first 3 occurrences of "cac" as shown: 

bacacbaacacac

bacacbaacacac

bacacbaacacac 

I am unable to calculate the value of s though.

 

Related questions

0 votes
2 answers
1
326 views
Let the difference between the maximum possible profit for $0/1$ knapsack and fractional knapsack with capacity $20$ be $X$. What is the value of $X$ Item a b c d e f g h i j Profit 7 10 3 3 26 19 18 17 5 4 Weight 3 5 2 1 12 10 9 9 4 1 How to solve for $0/1$ knapsack for the maximum profit in the faster way ???
asked Dec 23, 2018 in Algorithms jatin khachane 1 326 views
0 votes
0 answers
2
108 views
Which of the following procedure is suitable to find longest path from given vertex to any other vertex in Directed Acyclic Graph? Answer: Dynamic Programming. Why Greedy Algorithm cant be applied here?
asked Nov 26, 2018 in Algorithms Shamim Ahmed 108 views
1 vote
0 answers
3
111 views
Consider an OBST with n=4, p[1..4]={3,3,1,1} q[0..4]={2,3,1,1,1} Cost of OBST=___? Pls give the solution for this question.
asked Sep 10, 2018 in Algorithms Nidhi Budhraja 111 views
3 votes
2 answers
4
332 views
Consider two strings A = “abbaccda” and B = “abcaa” consider "x"be length of the longest common subsequence between A and B and “y” be the number of distinct such longest common subsequences between A and B. Then 10x+ 2y is ________.
asked Aug 1, 2018 in Algorithms talha hashim 332 views
...