1 of 18

Algorithm 2

TEXT LINE EDITING

(Computational Thinking)

Unit - 5

Dept. of CSE

PVPSIT, Kanuru.

2 of 18

  1. Problem
    1. Design and implement an algorithm that will search a line of text for a particular pattern or substring. Should the pattern be found it is to be replaced by another given pattern.
  2. Algorithm development The need to replace one string by another occurs very frequently in program and documentation preparation.
  3. Task is - To replace all occurrences on a line of a particular pattern by another pattern.

Department of CSE

2025-26

Algorithm 2

TEXT LINE EDITING

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 18

  1. Example:
      • Suppose we want to replace wrong by right in the line below:

“the two wrongs in this line are wrong” (original)

      • We would get:

“the two rights in this line are right” (edited line)

  • There are two phases to the text editing problem.
      • First stage - locating the pattern to be replaced
      • Second stage- actual replacement with the new pattern.

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 18

  1. We have:

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 18

  1. In our example above there are only four positions at which we can locate the pattern relative to the text.
  2. They are:

​

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 18

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 18

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 18

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 18

  1. The test we would apply is:

​

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 18

  1. Our central searching strategy has now evolved to:

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

11 of 18

  1. In our example the common parts are underlined.

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

12 of 18

  1. A complete-match signals the need to copy not from the original line but instead from the substitute pattern.
  2. So, in fact the two copying situations that we must deal with are well defined:

(a) When a mismatch copy from the original line.

(b) When a complete match copy from new pattern.

  • Let us consider the mismatch copy first. One proposal for the copy might be:

newtext[k] := txt[i]

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

13 of 18

  1. When we encounter a complete match we need to copy in a complete pattern rather than a single character.

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

14 of 18

  1. Assume Array Text contains the two wrongs in this line are wrong, Array wpattern contains wrong, Array rpattern contains right.
  2. i := 1; j := 1; patlength= length_of_wpattern; textlength= length_of_text;
  3. while (i <= textlength-patlength+1) do

if (wpattern[j] == Text[i+j-1]) then

j:= j+1

if (j == patlength+1) then

j:=1; k = 1

while (k <= patlength) do

Text[i]:=rpattern[k];

i := i+1;

k := k+1;

else

i := i+1

j := 1

Department of CSE

2025-26

Pseudocode

PVPSIT (Autonomous)

Problem Solving Techniques

15 of 18

  1. Assume Array Text contains the two wrongs in this line are wrong, Array wpattern contains wrong, Array rpattern contains right.
  2. Step 0: Start
  3. Step 1: Initialize patlength= length_of_wpattern; textlength= length_of_text;
  4. Step 2: Initialize Text Index i:=1 and WPattern Index j:=1.
  5. Step 3: Repeat Step 3.1 till (i <= textlength-patlength+1)

Step 3.1: if (wpattern[j] == text[i+j-1]) then do Steps 3.1.1 and 3.1.2 else go to 3.2

Step 3.1.1: j := j+1

Step 3.1.2: if (j == patlength+1) then do Steps 3.1.2.1 and 3.1.2.2

Step 3.1.2.1: j := 1; k := 1

Step 3.1.2.2: Repeat Steps 3.1.2.2.1, 3.1.2.2.2 and 3.1.2.2.3 till (k <= patlength)

Step 3.1.2.2.1: text[i]:=rpattern[k];

Step 3.1.2.2.2: i++;

Step 3.1.2.2.3: k++;

Step 3.2: j:=1;

Step 3.3: i:= i+1;

  • Step 4: Stop

Department of CSE

2025-26

Algorithm

PVPSIT (Autonomous)

Problem Solving Techniques

16 of 18

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

17 of 18

  1. Applications:
  2. Limited text searching.

Department of CSE

2025-26

PVPSIT (Autonomous)

Problem Solving Techniques

18 of 18

  1. 6.4.1 Implement a version of the current pattern searching algorithm that counts the number of times a given pattern occurs in a text. Your implementation should accommodate the fact that the search pattern may have repeating subsegments.

Department of CSE

2025-26

Supplementary problems (6.4.1)

PVPSIT (Autonomous)

Problem Solving Techniques