9. Let be a finite alphabet set, e.g., = {A, B, ... . Z} is the...

Transcribed Image Text:

9. Let be a finite alphabet set, e.g., = {A, B, "... . Z} is the set of 26 English alphabet symbols. A string x over is a concatenation of symbols from . E.g., x = NEVERODDOREVEN. We denote by xy the concatenation of x followed by y, and xm a concatenation of x by itself m times. E.g., for the above example, == NEVERODDOREVENNEVERODDOREVEN. x2 We want to solve the following computational question: Given two strings x and y over , are there positive integers m and n such that x = yn? Prove the following: |y| and n = |x|, the lengths of y and x (a) Such positive integers m and n exist iff it is true for m = respectively. From this derive a quadratic-time algorithm for this problem. (b) Suppose y |x|. If the answer to the problem is yes, then y is a prefix as well as a suffix of x. (c) The answer to the problem is yes iff the concatenations in two different orders are the same: xy = yx. Devise a linear-time algorithm from this. (Hint: To prove this condition is necessary, consider d = gcd(|x|, |y|).) 9. Let be a finite alphabet set, e.g., = {A, B, "... . Z} is the set of 26 English alphabet symbols. A string x over is a concatenation of symbols from . E.g., x = NEVERODDOREVEN. We denote by xy the concatenation of x followed by y, and xm a concatenation of x by itself m times. E.g., for the above example, == NEVERODDOREVENNEVERODDOREVEN. x2 We want to solve the following computational question: Given two strings x and y over , are there positive integers m and n such that x = yn? Prove the following: |y| and n = |x|, the lengths of y and x (a) Such positive integers m and n exist iff it is true for m = respectively. From this derive a quadratic-time algorithm for this problem. (b) Suppose y |x|. If the answer to the problem is yes, then y is a prefix as well as a suffix of x. (c) The answer to the problem is yes iff the concatenations in two different orders are the same: xy = yx. Devise a linear-time algorithm from this. (Hint: To prove this condition is necessary, consider d = gcd(|x|, |y|).)

Answer rating: 100% (QA)

a To prove that such positive integers m and n exist if and only if m divides x and n divides y we c... View the full answer