数据结构代写 |算法代写 | algorithm代写 | C代写 | C++代写: 这是一个利用C语言实现基础算法的题目
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
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:
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)