Substring Search Patterns in DSA Typescript - Deep Dive

Overview - Substring Search Patterns

What is it?

Substring search patterns are methods to find if a smaller string (called the pattern) exists inside a larger string (called the text). It helps locate where the pattern starts in the text or if it is not present at all. This is useful in many areas like searching words in documents, DNA sequences, or computer code. The goal is to do this search efficiently without checking every possible position one by one.

Why it matters

Without substring search patterns, computers would waste a lot of time checking every position in a text to find a pattern, which is slow for large texts. Efficient substring search saves time and resources, making software faster and more responsive. It powers search engines, spell checkers, and many tools we use daily. Without it, searching would be frustratingly slow and less practical.

Where it fits

Before learning substring search patterns, you should understand basic strings and loops. After this, you can learn advanced string algorithms like suffix trees or automata. This topic fits in the middle of string processing and algorithm optimization in your learning journey.

Mental Model

Core Idea

Substring search patterns are smart ways to find a small string inside a big string by avoiding needless repeated checks.

Think of it like...

It's like looking for a word in a book by quickly skipping pages where the word can't be, instead of reading every single page from start to end.

Text:  ┌─────────────────────────────┐
       │ a b c d a b c d a b c d e │
       └─────────────────────────────┘
Pattern:    ┌───────┐
           │ b c d │
           └───────┘
Search tries to align pattern over text and slide it right, skipping positions smartly when mismatch happens.

Build-Up - 7 Steps

1

Foundation

Understanding Basic String Matching

Concept: Learn the simplest way to find a pattern by checking every position in the text.

We start by placing the pattern at the beginning of the text. We compare each character one by one. If all characters match, we found the pattern. If a mismatch happens, we move the pattern one position to the right and try again. This repeats until the pattern fits inside the text or we reach the end.

Result

The pattern is found at the first position where all characters match, or not found if no full match exists.

Understanding the brute force method shows why naive search is slow and sets the stage for smarter methods.

2

Foundation

Implementing Naive Search in TypeScript

Concept: Write code that checks every possible position in the text for the pattern.

function naiveSearch(text: string, pattern: string): number { for (let i = 0; i <= text.length - pattern.length; i++) { let j = 0; while (j < pattern.length && text[i + j] === pattern[j]) { j++; } if (j === pattern.length) { return i; // pattern found at index i } } return -1; // pattern not found } // Example: naiveSearch('abcxabcdabxabcdabcdabcy', 'abcdabcy') returns 15

Result

The function returns the starting index of the pattern in the text or -1 if not found.

Writing the naive search helps see the direct approach and its inefficiency for large inputs.

3

Intermediate

Introducing the Knuth-Morris-Pratt Algorithm

🤔Before reading on: do you think skipping some checks after a mismatch can speed up search? Commit to yes or no.

Concept: KMP speeds up search by remembering where to restart after a mismatch using a precomputed table.

KMP builds a 'longest prefix suffix' (LPS) array for the pattern. This array tells how far to jump in the pattern when a mismatch happens, avoiding rechecking characters that we know match. During search, if a mismatch occurs, we use the LPS array to shift the pattern smartly instead of moving one by one.

Result

Search runs in linear time, O(n + m), where n is text length and m is pattern length, much faster than naive in worst cases.

Knowing how to reuse previous match information avoids repeated work and makes search efficient.

4

Intermediate

Building the LPS Array for KMP

🤔Before reading on: do you think the LPS array depends only on the pattern or also on the text? Commit to your answer.

Concept: The LPS array is built from the pattern alone and stores lengths of longest proper prefix which is also suffix for each prefix of the pattern.

function buildLPS(pattern: string): number[] { const lps = new Array(pattern.length).fill(0); let length = 0; // length of previous longest prefix suffix let i = 1; while (i < pattern.length) { if (pattern[i] === pattern[length]) { length++; lps[i] = length; i++; } else { if (length !== 0) { length = lps[length - 1]; } else { lps[i] = 0; i++; } } } return lps; } // Example: buildLPS('ababaca') returns [0,0,1,2,3,0,1]

Result

The LPS array guides how far to jump in the pattern after mismatches.

Understanding LPS construction is key to grasping how KMP avoids redundant comparisons.

5

Intermediate

Applying KMP Search with LPS Array

Concept: Use the LPS array during search to skip unnecessary checks and find the pattern efficiently.

function kmpSearch(text: string, pattern: string): number { const lps = buildLPS(pattern); let i = 0; // index for text let j = 0; // index for pattern while (i < text.length) { if (text[i] === pattern[j]) { i++; j++; if (j === pattern.length) { return i - j; // pattern found } } else { if (j !== 0) { j = lps[j - 1]; } else { i++; } } } return -1; // pattern not found } // Example: kmpSearch('abcxabcdabxabcdabcdabcy', 'abcdabcy') returns 15

Result

The function returns the starting index of the pattern or -1 if not found, running efficiently.

Combining LPS with search shows how precomputation speeds up real-time pattern matching.

6

Advanced

Exploring the Boyer-Moore Algorithm

🤔Before reading on: do you think starting comparisons from the end of the pattern helps skip more text? Commit to yes or no.

Concept: Boyer-Moore compares pattern from right to left and uses two heuristics to skip large parts of the text on mismatch.

Boyer-Moore uses the 'bad character' rule and 'good suffix' rule. When a mismatch happens, it shifts the pattern so that the mismatched character aligns with its last occurrence in the pattern or skips past matched suffixes. This often jumps far ahead, making it very fast in practice, especially for large alphabets.

Result

Search can skip many characters, often faster than KMP, especially on natural language texts.

Knowing how to use pattern structure and mismatch info to jump ahead drastically improves search speed.

7

Expert

Handling Complex Patterns and Unicode Texts

🤔Before reading on: do you think substring search algorithms work the same for all languages and character sets? Commit to yes or no.

Concept: Real-world texts include Unicode and complex characters, requiring adaptations in substring search algorithms.

Unicode characters can be multiple bytes and have combining marks. Algorithms must handle normalization and indexing carefully. Some implementations use code points or grapheme clusters instead of raw bytes. Also, patterns may include wildcards or regular expressions, requiring more advanced algorithms like Aho-Corasick or suffix automata.

Result

Substring search becomes more complex but remains efficient with proper handling of character encoding and pattern types.

Understanding text encoding and pattern complexity is crucial for building robust search tools in global applications.

Under the Hood

Substring search algorithms work by comparing characters of the pattern and text. Naive search checks every position. KMP precomputes a table (LPS) to know how far to jump after mismatches, avoiding rechecking matched characters. Boyer-Moore starts matching from the pattern's end and uses mismatch info to skip large parts of the text. Internally, these algorithms use arrays and pointers to track positions and shifts, minimizing redundant comparisons.

Why designed this way?

Early substring search was slow due to repeated checks. KMP was designed to reuse previous match info to avoid backtracking in the text. Boyer-Moore was created to exploit mismatches to skip ahead more aggressively. These designs balance preprocessing time with search speed, optimizing for different use cases and text types.

┌───────────────┐
│   Text        │
│ a b c d a b c │
│ d a b c d e f │
└─────┬─────────┘
      │
      ▼
┌───────────────┐
│   Pattern     │
│     b c d     │
└─────┬─────────┘
      │
      ▼
┌───────────────────────────────┐
│  Search Process                │
│  - Compare chars               │
│  - On mismatch:                │
│    * Naive: shift by 1         │
│    * KMP: shift using LPS      │
│    * Boyer-Moore: shift using │
│      bad character/good suffix │
└───────────────────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the naive substring search always take longer than KMP? Commit to yes or no.

Common Belief: Naive search is always slower than KMP in every case.

Reality: Naive search can be faster for small texts or patterns because it has no preprocessing overhead.

Why it matters: Assuming KMP is always better may lead to unnecessary complexity and slower performance in simple cases.

Quick: Does the LPS array depend on the text being searched? Commit to yes or no.

Common Belief: The LPS array changes depending on the text input.

Reality: The LPS array depends only on the pattern, not the text.

Why it matters: Misunderstanding this can cause confusion in implementing KMP and debugging.

Quick: Does Boyer-Moore always outperform KMP? Commit to yes or no.

Common Belief: Boyer-Moore is always faster than KMP.

Reality: Boyer-Moore is often faster on large alphabets and long texts but can be slower on small alphabets or short patterns.

Why it matters: Choosing the wrong algorithm without considering input characteristics can hurt performance.

Quick: Can substring search algorithms handle all Unicode texts without changes? Commit to yes or no.

Common Belief: All substring search algorithms work the same on any text encoding.

Reality: Unicode and complex encodings require special handling; naive algorithms may fail or give wrong results.

Why it matters: Ignoring encoding issues leads to bugs in internationalized software.

Expert Zone

1

The LPS array in KMP can be reused for multiple searches with the same pattern, saving preprocessing time.

2

Boyer-Moore's heuristics can be combined with other algorithms like Horspool or Sunday for tailored performance.

3

Handling overlapping patterns requires careful index management to avoid missing matches.

When NOT to use

Avoid KMP or Boyer-Moore when patterns include wildcards or regular expressions; use algorithms like Aho-Corasick or regex engines instead. For very short texts or patterns, naive search may be simpler and faster. When working with streaming data, incremental search algorithms or suffix automata are better choices.

Production Patterns

In real systems, substring search is often combined with indexing structures like suffix arrays or tries for fast repeated queries. Search engines use multi-level filtering with substring search as a component. Text editors implement incremental search using optimized substring algorithms for responsiveness.

Connections

Finite Automata

Substring search algorithms like KMP can be represented as finite automata that track pattern matching states.

Understanding substring search as state machines helps design efficient pattern matchers and connects to formal language theory.

Data Compression

Substring search patterns relate to finding repeated substrings, which is key in compression algorithms like LZ77.

Knowing substring search helps understand how compressors detect and encode repeated data efficiently.

Human Pattern Recognition

Humans also search for patterns in text or images by skipping irrelevant parts, similar to Boyer-Moore heuristics.

Studying substring search algorithms reveals parallels with cognitive processes in visual search and attention.

Common Pitfalls

#1 Checking pattern characters beyond text length causing errors.

Wrong approach:

for (let i = 0; i < text.length; i++) {
for (let j = 0; j < pattern.length; j++) {
if (text[i + j] !== pattern[j]) break;
if (j === pattern.length - 1) return i;
}
}
// This can access text[i + j] out of bounds when i + j >= text.length

Correct approach:

for (let i = 0; i <= text.length - pattern.length; i++) {
for (let j = 0; j < pattern.length; j++) {
if (text[i + j] !== pattern[j]) break;
if (j === pattern.length - 1) return i;
}
}

Root cause:

Not limiting the outer loop to positions where the pattern fits inside the text.

#2 Recomputing LPS array inside the search loop causing inefficiency.

Wrong approach:

function kmpSearch(text, pattern) {
for (let i = 0; i < text.length; i++) {
const lps = buildLPS(pattern); // recomputed every iteration
// search logic
}
}

Correct approach:

const lps = buildLPS(pattern); // compute once
function kmpSearch(text, pattern) {
// use lps in search loop
}

Root cause:

Not separating preprocessing from the search phase.

#3 Using substring search on raw UTF-8 bytes without decoding.

Wrong approach:

Searching pattern in a UTF-8 encoded byte array as if it were ASCII characters.

Correct approach:

Decode UTF-8 bytes to string first, then perform substring search on characters.

Root cause:

Ignoring character encoding and treating bytes as characters.

Key Takeaways

Substring search patterns help find smaller strings inside bigger ones efficiently by avoiding repeated checks.

Naive search is simple but slow; algorithms like KMP and Boyer-Moore use clever tricks to speed up search.

KMP uses a precomputed LPS array to know how far to jump after mismatches, saving time.

Boyer-Moore starts matching from the pattern's end and uses mismatch info to skip large parts of the text.

Handling complex texts like Unicode requires adapting substring search algorithms to avoid errors.

Practice

1. What is the main goal of substring search algorithms in strings?

easy

A. To sort all characters in a string alphabetically

B. To find if a smaller string exists inside a larger string

C. To reverse the entire string

D. To count the total number of vowels in a string

Solution

1. Step 1: Understand substring search purpose

   Substring search algorithms check if a smaller string (pattern) appears inside a bigger string (text).

2. Step 2: Compare options with substring search definition

   Only To find if a smaller string exists inside a larger string matches this goal. Sorting, reversing, or counting vowels are different tasks.

3. Final Answer:

   To find if a smaller string exists inside a larger string -> Option B

4. Quick Check:

   Substring search = find smaller string inside larger [OK]

Hint: Substring search means finding a smaller string inside a bigger one [OK]

Common Mistakes:

• Confusing substring search with sorting or reversing strings
• Thinking substring search counts characters
• Mixing substring search with string length calculation

2. Which of the following is the correct TypeScript syntax to check if string text contains substring pattern?

easy

A. text.includes(pattern)

B. text.contains(pattern)

C. text.has(pattern)

D. text.find(pattern)

Solution

1. Step 1: Recall TypeScript string methods

   TypeScript strings have a method called includes to check substring presence.

2. Step 2: Verify method names

   Only includes is valid. contains, has, and find are not string methods in TypeScript.

3. Final Answer:

   text.includes(pattern) -> Option A

4. Quick Check:

   Use includes() to check substring presence [OK]

Hint: Use includes() method to check substring in TypeScript [OK]

Common Mistakes:

• Using non-existent methods like contains() or has()
• Confusing includes() with find() which is for arrays
• Forgetting parentheses after method name

3. What will be the output of the following TypeScript code?

const text = "hello world";
const pattern = "wor";
console.log(text.indexOf(pattern));

medium

A. 6

B. -1

C. 3

D. 0

Solution

1. Step 1: Understand indexOf method

   indexOf returns the starting index of the substring if found, else -1.

2. Step 2: Find substring position in text

   In "hello world", substring "wor" starts at index 6 (0-based counting: h=0, e=1, l=2, l=3, o=4, space=5, w=6).

3. Final Answer:

   6 -> Option A

4. Quick Check:

   indexOf("wor") = 6 [OK]

Hint: indexOf returns start index or -1 if not found [OK]

Common Mistakes:

• Counting index starting from 1 instead of 0
• Confusing indexOf with includes (which returns boolean)
• Assuming indexOf returns substring length

4. Identify the error in the following TypeScript code snippet for substring search:

const text = "typescript";
const pattern = "script";
if (text.find(pattern)) {
  console.log("Found");
} else {
  console.log("Not Found");
}

medium

A. Using if statement without parentheses

B. Missing semicolon after console.log statements

C. Pattern variable is not declared

D. Using find() method on string which does not exist

Solution

1. Step 1: Check string methods in TypeScript

   Strings do not have a find() method. The correct method to check substring is includes() or indexOf().

2. Step 2: Verify other code parts

   Semicolons are optional in TypeScript, pattern is declared, and if statement syntax is correct.

3. Final Answer:

   Using find() method on string which does not exist -> Option D

4. Quick Check:

   Strings have includes(), not find() [OK]

Hint: Use includes() or indexOf(), not find() on strings [OK]

Common Mistakes:

• Assuming find() works on strings like arrays
• Thinking semicolons are mandatory causing errors
• Misreading if statement syntax

5. You want to find all starting indices of substring pattern in string text. Which approach correctly finds multiple occurrences in TypeScript?

hard

A. Use text.indexOf(pattern) once and return that single index

B. Use text.includes(pattern) repeatedly without changing index

C. Use a loop with indexOf(pattern, startIndex) updating startIndex after each find

D. Use text.findAll(pattern) method to get all indices

Solution

1. Step 1: Understand multiple substring search

   To find all occurrences, you must repeatedly search starting after the last found index.

2. Step 2: Analyze each option

   Use a loop with indexOf(pattern, startIndex) updating startIndex after each find uses a loop with indexOf and updates start index, which is correct. Use text.includes(pattern) repeatedly without changing index does not update index, so it loops infinitely or finds only once. Use text.indexOf(pattern) once and return that single index finds only one occurrence. Use text.findAll(pattern) method to get all indices uses a non-existent method.

3. Final Answer:

   Use a loop with indexOf(pattern, startIndex) updating startIndex after each find -> Option C

4. Quick Check:

   Loop with indexOf and updated start index finds all [OK]

Hint: Loop with indexOf and update start index to find all [OK]

Common Mistakes:

• Not updating start index causing infinite loops
• Using includes() which returns boolean, not index
• Expecting findAll() method which does not exist