[go: up one dir, main page]
Scribd
Upload
11 views1 page

Worksheet For String Processing

Worksheet for algorithms

Uploaded by

amarpeel33
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views1 page

Worksheet For String Processing

Worksheet for algorithms

Uploaded by

amarpeel33
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

CS-2009 Design and Analysis of Algorithms-Fall 2023

Worksheet- String Processing

Q1. Show the comparisons the naive string matcher makes for the pattern P = “010111”
in the text T = “1101011010101010111000011”.
Q2. Show
the complete working of Rabin-Karp Matching algorithms for the following pattern P and
Text T.

T= “596236810789458547897”
P= “7894”

1. Working modulo q =03


2. Working modulo q =19

Also show how many spurious hits the Rabin-Karp matcher encounters for both values of
q?

3. The suffix function σ(x) specifies the length of the longest prefix of pattern P that is also
a suffix of x.
Show the result of the following suffix function σ(x), for the pattern P = “ffaasstt”

i. σ(off)=2 ii. σ(cffa)=3

iii. σ(fast)= iv. σ(staaff)=

v. σ(pastt)= vi. σ(ttssaaff)=

vii. σ(ifffaa)= viii. σ(fffaasstt)=

ix. σ(fffaasst)= x. σ(fffaasstt)=

xi. σ(pakfffaasstt)= xii. σ(quettaafffaass)=

Q4: Compute the prefix function ∏ for the pattern


P=“bcadbbbabc”.
b. Find the above mentioned pattern
T=” bcabcabcabbabcbbcadbbbabccabbbbbabcbcabcc”
Show all steps.

You might also like