PRASAD V.
POTLURI SIDDHARTHA
INSTITUTE OF TECHNOLOGY
PROBLEM SOLVING
TECHNIQUES
By
B. Vinay Kumar
Assistant Professor
Dept. of CSE
PVPSIT, Kanuru.
PVPSIT (Autonomous)
Algorithm 2
TEXT LINE EDITING
• Problem
• 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.
• Algorithm development
• The need to replace one string by another occurs very frequently in program
and documentation preparation.
• The task is to replace all occurrences on a line of a particular pattern by
another pattern.
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
• 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.
1) First stage involves locating the pattern to be replaced and
2) Second stage involves the actual replacement with the new pattern.
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
• We have:
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
• In our example above there are only four positions at which we can locate
the pattern relative to the text.
• They are:
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
• The test we would apply is:
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
• Our central searching strategy has now evolved to:
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
• In our example the common parts are underlined.
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
• A complete-match signals the need to copy not from the original line but
instead from the substitute pattern.
• 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]
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
• When we encounter a complete match we need to copy in a complete
pattern rather than a single character.
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
Pseudocode PVPSIT (Autonomous)
• Assume Array Text contains the two wrongs in this line are wrong, Array
wpattern contains wrong, Array rpattern contains right.
• i := 1; j := 1; patlength= length_of_wpattern; textlength= length_of_text;
• 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 :=Techniques
Problem Solving 1 B. Vinay Kumar Friday, June 27, 2025
Algorithm PVPSIT (Autonomous)
• Assume Array Text contains the two wrongs in this line are wrong, Array wpattern contains
wrong, Array rpattern contains right.
• Step 0: Start
• Step 1: Initialize patlength= length_of_wpattern; textlength= length_of_text;
• Step 2: Initialize Text Index i:=1 and WPattern Index j:=1.
• 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
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
• Applications:
• Limited text searching.
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
PVPSIT (Autonomous)
Supplementary problems (6.4.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.
Problem Solving Techniques B. Vinay Kumar Friday, June 27, 2025
