You are given a string of n characters s[1 : : : n], which you believe to be a corrupted text document in which all punctuation

Question

1 month ago

12

You are given a string of n characters s[1 : : : n], which you believe to be a corrupted text document in which all punctuation

has vanished (so that it looks something like itwasthebestoftimes...). You wish to reconstruct the document using a dictionary, which is available in the form of a Boolean function dict(): for any string w, dict(w) = true if w is a valid word false otherwise . (a) Give a dynamic programming algorithm that determines whether the string s[] can be reconstituted as a sequence of valid words. The running time should be at most O(n2), assuming calls to dict take unit time. (b) In the event that the string is valid, make your algorithm output the corresponding sequence of words.

Computers and Technology

1 answer:

ivann1987 [1K] · Answer 1 · 2026-03-20T11:33:03+03:00

Response: explained in the explanation section

Explanation:

Given that:

Assume D(k) =║ true if [1::: k] is a valid sequence of words, or false otherwise

In determining D(n)

the sub problem s[1::: k] is a valid sequence of words IFF s[1::: 1] is valid and s[ 1 + 1::: k] is a valid word.

Thus, we derive that D(k) is defined by the following recurrence relation:

D(k) = ║ false max(d[l] ∧ DICT(s[1 + 1::: k]) otherwise

Algorithm:

Valid sentence (s,k)

D [1::: k] ∦ array of boolean variables.

for a ← 1 to m

do;

d(0) ← false

for b ← 0 to a - j

do;

if D[b] ∧ DICT s([b + 1::: a])

d (a) ← True

(b). Algorithm Output

if D[k] == True

stack = temp stack ∦stack assists in displaying the strings in order

c = k

while C > 0

stack push (s [w(c)]::: C] // w(p) denotes the index in s[1::: k] of the valid word // at position c

P = W (p) - 1

output stack

= 0 =

cheers, I hope this aids you!!!