FIT3155: Lab questions for week 2 (based on week 1’s topic)
Objectives: Develop a working implementation of Gusfield’s Z-algorithm Z-algorithm
1. Develop a set of test cases that targets all the different scenarios that might arise in the Z-algorithm i.e. the base case, case 1, case 2a, case 2b. An example is shown below.
str[0…5]: a b a b a c Z-values:- 0 3 0 1 0
Copyright By PowCoder代写 加微信 powcoder
Case: – base case case 1 case 2a case 2b case 1
2. Implement a naive algorithm for computing Z-values. You may find the pseudocode below helpful, but note that you might not want to explicitly store Z1.
naiveZ: input str [1…n]
n=|str| zValues(1) = n
for i from 2 to n:
zValues(i) for i from 2 to n: numMatches zValues(i)
return zValues
= compare ( s t r [ i . . . ] , s t r [ 1 . . . ] ) = numMatches
3. Often we need to access substrings of strings and it is common to use string slicing in python to do so. For instance to access the substring ‘xyz’ of the string str[0 . . . 4] = ‘axyzb’ we would write:
substring = str[1 : 4]
Discuss the complexity of string slicing, can you think of a situation where this might matter?
4. Implement the Z-algorithm. Your code should accept a string as input and return the Z-values for the string. You can reuse the comparison function you wrote in task 2 to make the comparisons required in the base case, case 1 and case 2b.
Exact pattern matching
1. Implement a na ̈ıve exact pattern matching algorithm (see pseudocode below).
n = |txt| m= |pat|
for i from 1 to n−m+1 do for j from 1 to m do
if txt[i+j−1] != pat[j] then break // mismatch
endif endfor ;
if (j ==m+1) print i; endfor
2. Implement the Z-algorithm based exact pattern matching discussed in lectures.
Bonus tasks
1. Write a program to generate a random string of any stated length n from a binary alphabet {H,T}, with the probability of character H being p (and hence probability of T is 1 − p). Your program should take n and p as arguments to write out a random string to a file
2. Test the wall clock times of your pattern matching algorithm imple- mentation above, on large random strings (say > 1, 000, 000 characters) together with randomly generated short patterns (say 10 characters). Vary n and p to empirically test the effect on the observed runtimes.
3. If you have finished this set, consider going through your tute sheet and implement some of the algorithmic exercises into practice.
-=0=- END -=0=-
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com