# Gateforum Test Series: Algorithms - Dynamic Programming

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 ________

edited

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

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 ???