数据结构代写 |算法代写 | algorithm代写 | C代写 | C++代写-pattern-matching algorithm

Implement the pattern-matching algorithm shown in the pseudo-code listing below. The ‘slist’ object in the pseudo-code is a map data structure. Most listings of this algorithm’s use arrays, however, a map is much more space efficient.

Your map data structure is your dynamic-array, converted to a map that takes pairs as data members. Also, the map is implemented as a hash-table. The midterm contained a hash-table section that handled unique-string combinations. For this map, design your hashing function to handle ‘unique strings’ of length 1 thru 8.

This algorithm expects unique strings of length 1 (the lower ascii table). Test your implementation using a range of text strings and patterns. For testing purposes, assume the strings are unique and you do not need to check for uniqueness.

A second test would be to test unique strings of length > 1. Note that a unique string is a string that contains unique characters not present in other strings. For example: , , are unique strings of length 3, while ,, are not unique.

See algorithms below for pseudo-code. Also, the uploaded sample code for Rabin-Karp (RabinKarp.cpp), has a bug in the implementation: sometimes it finds a match, and sometimes it doesn’t. It should always find it, as it’s a character-by-character crawler. Part 2 of this assignment is to fix bug, so it finds it in all cases.

Algorithm Position(c, s, t)
1 for o = len(t)+1 to 1 dec o
2 f = true
3 for i = 0 to len(s) step i
4 it = o – len(s) – 1 + i
5 if it >= 0 and s[i] != t[it]
6 f = false
7 it = o – len(s) – 1
8 if f == true and (it<=0 or t[it-1] ne c) 9 return len(t) - o + 1 10 return -1 Algorithm BadShift(p) 1 for x = 0 to len(p)-1 step 1 2 slist[p[x]] = len(p) - x - 1 Algorithm GoodShift(k) 1 b = "" 2 for i = 0 to len(k) step 1 3 slist[len(b)] = Position(k[len(k) - 1 - i],b,k) 4 b = k[len(k) - 1 - i] + b 5 return slist Algorithm Search(t,p) 1 g = GoodShift(p) 2 b = BadShift(p) 3 while i < len(t) - len(p) + 1 4 j = len(p) 5 while j > 0 && p[j-1] == t[i+j-1]
6 j -= 1
7 if j > 0
8 bs = b[t[i+j-1]]
9 gs = g[len(p)-j]
10 if bs > gs
11 i += bs
12 else
13 i += gs
14 else
15 return i
16 return -1

Algorithm Test()
1 target = “block of text …”
2 pattern = “some pattern”
3 Search(target,pattern)