MODULE 4 PROBLEMS
1. For the given sample text, identify vocabulary and occurrence list, and build inverted
index using standard trie.
Sample text: “This is a text. A text has many words. Words are made from letters”.
Solution :
Vocabulary List Occurrence List
Letters 60
Made 50
Many 28
Text 11,19
words 33,40
2. For the given sample text, identify suffixes for given position, and build inverted
index using suffix trie and suffix tree.
SOLUTION:
Suffixes:
text. A text has many words. Words are made from letters.
many words. Words are made from letters.
made from letters.
Letters
3. Find the positions of the pattern in the text using Brute Force technique.
Text: ABRACABRACADABRA
Pattern: ABRACADABRA
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
A B R A C A B R A C A D A B R A
Mismatch at 7th Position. Slide window
A B R A C A D A B R A
to 2nd position & compare.
Mismatch. Slide window to
A B R A C A D A B R A
3rd position. & Compare.
Mismatch. Slide window to
A B R A C A D A B R A
4th position. & Compare.
A Mismatch. Slide window to
A B R A C A D A B R
5th position. & Compare.
A B R A C A D A B R A Mismatch. Slide window to
6th position. & Compare.
A B R A C A D A B R A
Pattern matched.
Pattern found at 6th position.
Time complexity of brute force for pattern matching is O(mn)
4. Calculate prefix function and find the positions of the pattern in the text using
Knuth- Morris-Pratt (KMP) algorithm.
Text: AGCGCGCGCTA
Pattern: GCGCTA
Step 1: construct prefix function table for the given pattern
1 2 3 4 5 6
Ch G C G C T A
PF 0 0 1 2 0 0
Step 2: Matching
1 2 3 4 5 6 7 8 9 10 11
A G C G C G C G C T A
i=1
Mismatch at j=1, since first letter has
1 2 3 4 5 6
no prefix, shift window to 2nd
G C G C T A position and start comparing.
j
i =2
1 2 3 4 5 6 Mismatch at j=5, calculate new
position i= i +( j-1) – PF(j-1)
G C G C T A
i= 2+ (5-1) – PF (5-1) = 2+4-2=4
j
i =4
Mismatch at j=5
1 2 3 4 5 6
G C G C T A i= 4+ (5-1) – PF (5-1)
j i = 4+4-2=6
i=6
1 2 3 4 5 6
G C G C T A
j
Pattern found at 6th position.
5. Calculate prefix function and find the positions of the pattern in the text using
Knuth- Morris-Pratt (KMP) algorithm and Boyer Moore Algorithm.
Text: ABRACABRACADABRA
Pattern: ABRACADABRA
I) KMP Algorithm:
Step 1: construct prefix function table for the given pattern
1 2 3 4 5 6 7 8 9 10 11
Ch A B R A C A D A B R A
PF 0 0 0 1 0 1 0 1 2 3 4
Step 2: Matching
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
A B R A C A B R A C A D A B R A
i=1
1 2 3 4 5 6 7 8 9 10 11
A B R A C A D A B R A
j
Mismatch at j=7, calculate new
position i= i +( j-1) – PF(j-1)
i= 1+ (7-1) – PF (7-1) = 1+6-1=6
i=6
1 2 3 4 5 6 7 8 9 10 11
A B R A C A D A B R A
j
Pattern found at 6th position.
II) Boyer Moore Algorithm
Text: ABRACABRACADABRA
Pattern: ABRACADABRA
Step 1: construct last occurrence function table for the given pattern
0 1 2 3 4 5 6 7 8 9 10
A B R A C A D A B R A
Ch A B C D R *
Last 10 8 4 6 9 -1
Step 2: Matching – match backwards
Initially start from i=10 & j=10
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B R A C A B R A C A D A B R A
0 1 2 3 4 5 6 7 8 9 10
A B R A C A D A B R A
j
Mismatch at j=9, calculate new pos
i= i+ m- min (j,1+last(T(j)) )
i= 9+ 11 – min (9, 1+last (C) )
= 20 – min (9, 1+4)
i= 20 – 5= 15
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B R A C A B R A C A D A B R A
0 1 2 3 4 5 6 7 8 9 10
A B R A C A D A B R A
j
i
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B R A C A B R A C A D A B R A
0 1 2 3 4 5 6 7 8 9 10
A B R A C A D A B R A
j
Since j=0 , pattern found at i+1 = 5+1= 6th position.
6. For the given Text and pattern,
Text: AABAACAABA
Pattern: AABA
1. Construct Non-Deterministic Automaton
2. Write Associated B Table.
3. Find the positions of the pattern in the text using Shift OR algorithm.
Solution:
Pattern: AABA
B Table:
Ch b1 b2 b3 b4 Bitmask
b4b3b2b1
A 0 0 1 0 0100
B 1 1 0 1 1011
* 1 1 1 1 1111
1 2 3 4 5 6 7 8
Matching Table : Text : A A B A A C A A
Initial State j Tj B[Tj] D<<1 D<<1 | B[Tj]
D
1111 1 A 0100 1110 1110
1110 2 A 0100 1100 1100
1100 3 B 1011 1000 1011
1011 4 A 0100 0110 0110
left most bit zero=pattern found
After match start with next character in text hence D= 1111
1111 2 A 0100 1110 1110
1110 3 B 1011 1100 1111 1111=next character of text
1111 3 B 1011 1110 1111
1111 4 A 0100 1110 1110
1110 5 A 0100 1100 1100
1100 6 C 1111 1000 1111
1111 5 A 0100 1110 1110
1110 6 C 1111 1100 1111
do it further for other characters......
Pattern found at 4th position.
7. For the given data, find out whether pattern P occurs in Text T with at most k
errors using the dynamic programming algorithm.
Text T= surgery
Pattern P= survey
Errors k=2
C [0, j] =0
C[i,0] =i
C [i, j] = if (P = T ) then C [i-1, j-1]
i j
else 1+min (C [i -1, j], C[i, j-1], C[i -1, j-1])
S U R G E R Y
0 0 0 0 0 0 0 0
S 1 0 1 1 1 1 1 1
U 2 1 0 1 2 2 2 2
R 3 2 1 0 1 2 2 3
V 4 3 2 1 1 2 3 3
E 5 4 3 2 2 1 2 3
Y 6 5 4 3 3 2 2 2
Pattern matches text with error distance of 2.
This 8th problem is not part of your syllabus
8. For the given Text and pattern,
Text: aadaacaabaaba
Pattern: aaba
Find the positions of the pattern in the text using Backward matching (BDM)algorithm.
Step1 : Reverse the pattern and write the suffixes
Pr: - abaa
Suffix (Pr):- abaa, baa, aa, a
Step2 : construct suffix automata for these suffixes
Step 3: start matching using BDM technique
Pattern found at 7th and 10th position.