Gateforum Test Series: Algorithms - Dynamic Programming

Question

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 ________

Answer 1

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.

Answer 2

s =2 + 8 + 10 = 20

Comments

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.