1 of 26

PROBLEM SOLVING TECHNIQUES

By

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY

2 of 26

  • Problem
  • Design and implement an algorithm that will efficiently search a given text for a particular keyword or pattern and record the number of times the keyword or pattern is found.
  • Algorithm development
  • (inefficient approach)
  • In looking for the keyword SENTENCE in the text

Dept of CSE

2025 - 26

Algorithm 4

SUBLINEAR PATTERN SEARCH

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 26

  • One approach that we can take may proceed as follows.
  • Test if the first character in the word matches the first character in the text (e.g. compare S and T).
  • If they do not match, compare the first character in the word with the second character in the text (e.g. compare S and H) and so on.
  • When the first character in the word matches the current character in text (e.g. S of SENTENCE matches S of SLOW) we then compare the second character in the word with the next character in the text (in this case E with L) and so on.
  • “is there a better way of implementing a text searching algorithm?”

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 26

​

​

​

  • If SENTENCE were to end at character position 16 then the 16th text character would need to be an E.
  • Instead we find an R which again is not in the word SENTENCE.
  • This means that the next place that the word SENTENCE could end is at text position 24.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 26

​

​

​

  • At text position 24 we encounter a T.
  • This is not an E so SENTENCE cannot end at position 24.
  • The question is where is the next possible position that the word SENTENCE could end?
  • This case is the case where T is encountered in the word SENTENCE.
  • It is possible that T just encountered in the text may belong to the text as follows:

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 26

​

​

  • To check out if the T at position 24 really does belong to the word SENTENCE we could again look at the position where the last character of the word would be expected (in this case character 28).
  • At position 28 we encounter a K instead of an E.
  • From this we can conclude that the T at position 24 did not really belong to the word SENTENCE.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

11 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

12 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

13 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

14 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

15 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

16 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

17 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

18 of 26

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

19 of 26

Problem Statement

We are provided with an input pattern and a text (or string), and we need to search and print all the occurrences of the pattern in the string.

Note: Use Boyer Moore's algorithm for searching the pattern in the string.

  • The first input is the size of the actual string i.e. n.
  • The second input is the size of the pattern string i.e. m.
  • The third input contains the actual string.
  • The fourth input contains the pattern to be searched.

​

PVPSIT (Autonomous)

Problem Solving Techniques

20 of 26

Example

Let us look at some of the examples provided to search for a pattern searching using the Boyer-Mooreoore algorithm.

Example 1: text = "Scaler Topics" pattern = "Topics"

Output: Pattern found at index: 7.

Example 2: text = "he is doing what he was told to do" pattern = "he"

Output: Pattern found at index: 0.

Pattern found at index: 17.

​

PVPSIT (Autonomous)

Problem Solving Techniques

21 of 26

For example,

let's say that the pattern given is: RPCRQ

the input text is: AYRRQMGRQRQ

Approach 1: Bad Character Heuristic

Source - https://www.scaler.com/topics/boyer-moore-algorithm/

PVPSIT (Autonomous)

Problem Solving Techniques

22 of 26

For example,

let's say that the pattern given is: RPCRQ

the input text is: AYRRQMGRQRQ

Approach 1: Bad Character Heuristic

Source - https://www.scaler.com/topics/boyer-moore-algorithm/

PVPSIT (Autonomous)

Problem Solving Techniques

23 of 26

1. Pre-processing Phase (Bad Character Table)

  • Initialize an array (or hash map) badCharacter of size 256 (for all ASCII characters) with the value -1.
  • Iterate through the pattern P of length m:
    • For each character at index i, update badCharacter[P[i]] = i.
    • Result: This stores the index of the last occurrence of every character present in the pattern.

​

Boyer-Moore Algorithm (Bad Character Heuristic)

PVPSIT (Autonomous)

Problem Solving Techniques

24 of 26

2. Initialization

  • Let the text be T with length n, and the pattern be P with length m.
  • Set the initial alignment shift s = 0.

3. Searching Phase

While the shift s is less than or equal to (n - m):

  1. Initialize an index j = m - 1 (starting from the rightmost character of the pattern).
  2. Compare characters: While j >= 0 and P[j] == T[s + j]:
    • Decrement j (move backward).
  3. Check for Match:
    • If j < 0 (Match Found):
      • Report the current shift s as a match position.
      • Calculate next shift: Shift the pattern so the next character in the text aligns with its last occurrence in the pattern. If it exceeds the text length, shift by 1.
    • Else (Mismatch):
      • Identify the "Bad Character" in the text at T[s + j].
      • Calculate Shift: Move the pattern to the right by max(1, j - badCharacter[T[s + j]]).
      • This ensures the pattern shifts forward to align the mismatching text character with its last known position in the pattern.

4. Termination

  • Return all found indices or end the process once the shift s exceeds the searchable boundary of the text.

Boyer-Moore Algorithm (Bad Character Heuristic)

PVPSIT (Autonomous)

Problem Solving Techniques

25 of 26

  • Why this is efficient
    1. The "magic" happens in the shift calculation:
    2. shift = max(1, j - badCharacter[T[s + j]])
    3. By looking at the character that caused the mismatch, Boyer-Moore can often "skip" large sections of the text, sometimes achieving sub-linear time complexity—meaning it doesn't even have to look at every character in the string to find the pattern!

Boyer-Moore Algorithm (Bad Character Heuristic)

PVPSIT (Autonomous)

Problem Solving Techniques

26 of 26

  • Applications
  • Text editors, pattern matching, keyword searching.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques