Task #2: Text Match Given two strings 8, 7, the following algorithm prints all indices i such that s appears as a substring oft starting at index i into t. Unlike the previous exercise, the pseudocode uses 0-based indexing for arrays and strings, like in C++. You are strongly encouraged to try tracing the execution of this algorithm on an example. To get an idea of what this algorithm does, Phase 1 computes an array step, where stepi] is the largest k such that the first k +1 characters of s[0...,) and the last k +1 characters of 80....] form the same string. Note it could be that steplk] = -1. Then Phase 2 uses stepl] to find all occurrences of s as a substring of t. It does this by maintaining values m and i. At the start of each iteration of the outer loop, m will be the greatest integer such ing so...m matches ti-m-1...i-1]. It tries to match the next character i.e. checks if sm + 1) = t[i), if it cannot it steps m back to the "next" possible match at position stepm) and repeats the check until either sm + 1] = ti or m = -1. The running time of this algorithm is linear: O(length(s) + length(t)). That may not be clear initially from the pseudocode. Implement a function void textMatch(const char *s, const char *t) in a file textmatch.cpp that accepts two character arrays holding null-terminated strings and prints all of the indices 0 Si may also be helpful. Your solution should also read two nonempty strings with at most 100,000 characters each. It should then call your implementation of textMatch Some sample inputs and outputs for the function are provided below. The third example also describes the values of stepl for that example, to help you debug Algorithm text Match(s, t) Phase 1: Computing stepl step(0 -1 k -1 for i from 1 to length(s) - 1 do while k > 0 and 8[k +1] s[i] do k stepk] if s[k + 1] = s[i] then kk +1 step[i] + k Phase 2: Finding the Matches m -1 for i from 0 to length(1) - 1 do invariant: m is greatest s.t. 8[0...m] = t[i-m-1... - 1 while m > 0 and s(m + 1] #t[i] do mt step[m if s[m + 1] = t[i] then mm +1 if m = length(s) - 1 then print(i+1-length(s)) m step[m] Input 1 Output 1 1 3 7 an bananaban Task #2: Text Match Given two strings 8, 7, the following algorithm prints all indices i such that s appears as a substring oft starting at index i into t. Unlike the previous exercise, the pseudocode uses 0-based indexing for arrays and strings, like in C++. You are strongly encouraged to try tracing the execution of this algorithm on an example. To get an idea of what this algorithm does, Phase 1 computes an array step, where stepi] is the largest k such that the first k +1 characters of s[0...,) and the last k +1 characters of 80....] form the same string. Note it could be that steplk] = -1. Then Phase 2 uses stepl] to find all occurrences of s as a substring of t. It does this by maintaining values m and i. At the start of each iteration of the outer loop, m will be the greatest integer such ing so...m matches ti-m-1...i-1]. It tries to match the next character i.e. checks if sm + 1) = t[i), if it cannot it steps m back to the "next" possible match at position stepm) and repeats the check until either sm + 1] = ti or m = -1. The running time of this algorithm is linear: O(length(s) + length(t)). That may not be clear initially from the pseudocode. Implement a function void textMatch(const char *s, const char *t) in a file textmatch.cpp that accepts two character arrays holding null-terminated strings and prints all of the indices 0 Si may also be helpful. Your solution should also read two nonempty strings with at most 100,000 characters each. It should then call your implementation of textMatch Some sample inputs and outputs for the function are provided below. The third example also describes the values of stepl for that example, to help you debug Algorithm text Match(s, t) Phase 1: Computing stepl step(0 -1 k -1 for i from 1 to length(s) - 1 do while k > 0 and 8[k +1] s[i] do k stepk] if s[k + 1] = s[i] then kk +1 step[i] + k Phase 2: Finding the Matches m -1 for i from 0 to length(1) - 1 do invariant: m is greatest s.t. 8[0...m] = t[i-m-1... - 1 while m > 0 and s(m + 1] #t[i] do mt step[m if s[m + 1] = t[i] then mm +1 if m = length(s) - 1 then print(i+1-length(s)) m step[m] Input 1 Output 1 1 3 7 an bananaban