The Gateway to Computer Science Excellence
0 votes
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 ________
in Algorithms by Active (4.7k points)
edited by | 100 views

2 Answers

+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.

 

0 votes

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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,601 answers
195,855 comments
102,228 users