100 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 | 100 views

+1 vote

s =2 + 8 + 10 = 20

by (205 points)
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.

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.

by (41 points)