The following algorithm finds the initial substring of y that can be reversed and found in y. For example, longestInitialReverseSubstringLength(“aabaa”) = 5, because “aabaa” is the same string forwards and backwards, so the longest initial substring that can be reversed and found in the string is “aabaa”. Also, longestInitialReverseSubstringLength(“bbbbababbabbbbb”) is 6, because “babbbb” can be found in the string (see color-highlighted portions of the string), but no longer initial string exists reversed in any part of the string.
longestInitialReverseSubstringLength(String y)
01 Max ← 0; //this will be our answer.
02 for i ← 1 to y.length() do: //loop (Main) tries to find reversed initial substrings of...
03 x ← empty string //...all possible lengths
04 for r ← i to 1 do: //reverses the initial i characters and stores in x
05 x ← x○y[r] // “○” indicates concatenation.
06 end for //end reversal loop
07 found ← false;
08 for j ← 1 to y.length() - x.length() + 1 do: //loop (A), which searches for x in y.
09 f ← true //unless contradicted, assume x is in y.
10 for k ← 1 to x.length() do: // loop (B), which searches y[j...j+k] for x.
11 if y[j+k] ≠ x[k] then: //there is a mismatch...
12 f ← false //so x was not found.
13 end if
14 end for //end loop (B)
15 if f then: //x was in y
16 found = true //remember it
17 break
18 end if
19 end for // ends the loop (A)
20 if found then: max = i //***Note the assignment*** new max length found.
21 end for //end loop (Main).
22 return max; //return the answer.
end function
show your program running and taking 1 second to run.
Analyze the algorithm’s runtime mathematically and express the runtime using big-oh notation (provide a tight upper bound).
Analyze the function experimentally.
Implement the algorithm
Let x be the string length at which your program takes 2 seconds to run, collect running times for your algorithm using the following string lengths: x/4, 2x/4, 3x/4, x, 5x/4, 6x/4, 7x/4, 2x.
Generate your strings by reading the attached file, only reading as many characters as you need.
Plot your results (x-axis is string length, y-axis should be time)
Draw conclusions based on your graph. You may also need to plot another curve (e.g., n, n2, or n3, to support your conclusions).
Give the runtime of the following algorithm, which calculates the average of an array of length 100. Note, importantly, this function only works if the length of A is 100.
average(A) :
If length(A) != 100 then:
ERROR
End If
Sum ← 0
For x in A do:
Sum ← Sum + x
End For
Return Sum / 100
end average
Here is your code what you wanted from the above algorithm.
import sys
def printSubStr(st, low, high) :
sys.stdout.write(st[low : high + 1])
sys.stdout.flush()
return ''
def longestInitialReverseSubstringLength(st) :
n = len(st)
table = [[0 for x in range(n)] for y
in range(n)]
maxLength = 1
i = 0
while (i < n) :
table[i][i] = True
i = i + 1
start = 0
i = 0
while i < n - 1 :
if (st[i] == st[i + 1]) :
table[i][i + 1] = True
start = i
maxLength = 2
i = i + 1
k = 3
while k <= n :
i = 0
while i < (n - k + 1) :
j = i + k - 1
if (table[i + 1][j - 1] and
st[i] == st[j]) :
table[i][j] = True
if (k > maxLength) :
start = i
maxLength = k
i = i + 1
k = k + 1
print( printSubStr(st, start, start + maxLength - 1) )
return maxLength
st = input("Enter your string : - ")
l = longestInitialReverseSubstringLength(st)
print( l )
Get Answers For Free
Most questions answered within 1 hours.