Create a program that searches user inputted substring within the text. Requirem

Question

Create a program that searches user inputted substring within the text.

Requirements:

Program should read the text from file (number of characters > 200).

User should be able to search different substrings in the same file (looping).

The search should be implemented using one of the following algorithms (do not use built-in search

functions!!!):

Knuth-Morris-Pratt algorithm (highest possible mark 10).

If substring is found, then program should output its start position in the text. If substring is not found, then program should output appropriate message.

Explanation / Answer

Knuth-Morris-Pratt algorithm:-

    input:

        an array of characters, S (searched)

        an array of characters, W (word sought)

    output:

        an integer (here the zero-based position in S at which the W is found)

    define variables:

        an integer, k ? 0

        an integer, x ? 0

        an array of integers, T

    while k+ x < length(S)

    do

        if W[x] = S[k + x]

       then

            if x = length(W) - 1

         then

                return k

            let x ? x + 1

        else

            if T[x] > -1 then

                let k ? k + x - T[x], x ? T[x]

            else

                let x ? 0, k ? k + 1

               return S(x);

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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