What is String Matching? String, Substring, and Proper Substring Explained

In computer science, string matching is one of the most important topics in algorithms and data structures. It is used in almost every application that deals with text, such as word processors, web search engines, and pattern recognition systems. The main goal of string matching is to find the location or occurrence of a pattern (small string) within a larger text (big string).

For example, finding the word “book” in a sentence like “I am reading a good book.”

To understand string matching properly, we must first understand what a string, substring, and proper substring mean. These are basic building blocks used in text-processing algorithms like Naive Search, KMP, Rabin-Karp, and Finite Automata based methods

Quescol 1-Minute Read

String Matching is the process of finding a smaller string (pattern) inside a larger string (text) to check if it exists and where it occurs. A string is a sequence of characters like letters, digits, or symbols. A substring is any continuous sequence of characters within a string, while a proper substring is a substring that is smaller than the original string.

For example, in “COMPUTER”, “COM” and “PUT” are substrings, and “COM” is a proper substring.

Key Points:

• String: Sequence of characters (letters, digits, symbols).
• Substring: Continuous part of a string.
• Proper Substring: Substring smaller than the original string.
• Pattern: The string we are searching for.
• Text: The larger string in which we search.
• Goal: Find if the pattern exists and its positions in the text.
• Applications: Word processors, search engines, pattern recognition, bioinformatics.
• Algorithms: Naive Search, KMP, Rabin-Karp, Finite Automata.

Let’s Understand in Depth

What is String Matching?

String matching is the process of finding a smaller string (called a pattern) within a larger string (called a text).

In another word, we can also explain it as String matching refers to finding occurrences of a pattern string within a larger text string.

The goal is to determine:

1. Whether the given pattern/smaller string exists in the larger string.
2. If yes, at what position(s) it occurs.

For example:

• Text (T): “AABAACAADAABAABA”
• Pattern (P): “AABA”

The pattern appears in the text at positions: 0, 9, and 12.

Types of String Matching Algorithms

1. Naive String Matching

• Checks the pattern at every position in the text.
• Simple but slow for large text.
• Example: Searching “cat” in “concatenate” by comparing each letter.

2. Knuth-Morris-Pratt (KMP) Algorithm

• Uses a preprocessed table (LPS array) to skip unnecessary comparisons.
• Faster than naive because it avoids re-checking matched characters.
• Example: Searching “ABABC” in “ABABABC”.

3. Rabin-Karp Algorithm

• Uses a hash function to convert strings into numbers.
• Compares hash values first; if they match, then checks the string.
• Good for searching multiple patterns at once.

4. Boyer-Moore Algorithm

• Starts comparing from the end of the pattern.
• Skips parts of the text based on mismatched characters.
• Very fast in practice for large texts.

5. Finite Automata Based Algorithm

• Builds a machine (states and transitions) to recognize the pattern.
• Efficient for repeated searches but requires extra memory for the automaton.

6. Aho-Corasick Algorithm

• Designed for searching multiple patterns simultaneously.
• Builds a trie (tree) of patterns and uses failure links to search fast.
• Common in virus scanning and keyword searching.

7. Bit-Parallel Algorithms (Shift-Or / Shift-And)

• Uses bitwise operations to match patterns quickly.
• Works best for short patterns.

What is String?

A string is a sequence of characters arranged in a specific order. These characters can be letters, digits, symbols, or spaces.

Formally,

A string is a finite sequence of symbols chosen from a given set called an alphabet.

For example:

• “HELLO” is a string made of 5 characters: H, E, L, L, O
• “12345” is a string made of digits
• “A@B#” is a string made of letters and special characters

In most programming languages, a string is treated as an array (or list) of characters.
Example in Java:

String text = "HELLO";

Here,

• text.charAt(0) = ‘H’
• text.charAt(1) = ‘E’, and so on.

So, a string simply represents data made of characters arranged one after another.

What is Substring?

A substring is a smaller portion or segment of a larger string. It is formed by taking a continuous part of the main string without changing the order of characters.

Formally,

A substring of a string S is a sequence of characters that occurs consecutively within S.

For example:
If S = “COMPUTER”, then

• “COM” is a substring
• “PUT” is a substring
• “ER” is also a substring
• But “CPT” is not a substring (characters are not consecutive)

In Java, you can extract a substring using the substring() method:

String s = "COMPUTER";
System.out.println(s.substring(0, 3)); // Output: COM
System.out.println(s.substring(3, 6)); // Output: PUT

What is Proper Substring?

A proper substring is any substring of a string that is not equal to the string itself.

Formally,

If S is a string, then every substring of S that is shorter than S is called a proper substring.

For example:
If S = “APPLE”, then:

• “APP” is a proper substring
• “PLE” is a proper substring
• “APPLE” is not a proper substring (it’s the full string itself)

So, the rule is simple:
Every proper substring is a substring, but not every substring is a proper substring.

Conclusion

String matching is a fundamental concept in computer science that helps us efficiently search for patterns within text. Mastering it is important because it forms the basis for advanced algorithms and practical applications in areas like search engines, data analysis, and bioinformatics. Understanding string matching thoroughly makes learning complex algorithms easier and improves problem-solving skills in text processing tasks.