Let T = t1t2 . . . tn and P = p1p2 . . . pm (m n) be two text strings composed o

Question

Let T = t1t2 . . . tn and P = p1p2 . . . pm (m n) be two text strings composed of letters from (say) the English alphabet. We wish to decide whether P is a substring of T, i.e., whether the letters of P appear consecutively in T. (For instance, if T is MINNESOTA and P is INNE, then P is a substring; if P is INEN, then it is not.) This is a common task in text editors. Your goal is to develop a simple algorithm that outputs “yes”/“no” depending on whether or not P is a substring of T. Your algorithm should make no more than m × n comparisons between letters from P and T. (a) Describe your approach in a few sentences and give pseudocode. Your style of pseudocode should be similar to the one in the text or seen in class; do not give full-blown C/C++/Java etc. (b) Analyse your algorithm and show that it makes no more than the stated number of comparisons between letters of the two strings. (Ignore any other type of operation.)

Explanation / Answer

/* Let length of string s be n and length of string t be m
   run the loop which temninate at the difference of length of two strings of length m and n
   the second for loop is nested inside the first which check if the substring exists .
   return true if substring exist
   else return false after the for loop is terminated
*/

bool IsSubstring (string s, string t)
{
for (int i = 0; i <= (s.Length - t.Length); i++)
{
bool found = true;

for (int j = 0; found && j < t.Length; j++)
{
if (s[i + j] != t[j])
found = false;
}

if (found)
return true;
}

return false;
}

Observing the code above , the first loop runs for the
difference between the length of the the strings and
the nested loop runs till the end of second string for every element in first string.
Therefore the algorithm makes no more than the n *m
number of comparisons between letters of the two strings.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.