Prefix Substring

A prefix substring of a string is a substring that is present at the beginning of the string. It represents the initial sequence of characters in the string before any other substrings. Some examples:

• In the string “algorithm”, “algo” is a prefix substring.

• In “computer”, “com” and “comp” are prefix substrings.

• The empty string "" is a prefix substring of any string.

Prefix substrings are useful in many string algorithms and data structures. Some applications include:

• String searching - Checking if a pattern matches a prefix can eliminate unnecessary further comparisons.

• Autocomplete - Storing all prefix substrings allows quickly finding suggestions.

• Trie data structure - Efficiently stores strings by prefix substrings in tree form.

Example in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

String str = "hello";

// "he" is a prefix substring  
String prefix = str.substring(0, 2); 

// Check if prefix matches
if(str.startsWith(prefix)) {
  System.out.println(prefix + " is a prefix"); 
}

// Trie stores strings by prefix substrings
Trie trie = new Trie();
trie.insert("hello");
trie.contains("he"); // true

Example in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

string str = "algorithm";

// "algo" is a prefix substring
string prefix = str.substr(0, 4);

// Check match 
if (str.find(prefix) == 0) {
  cout << prefix << " is a prefix" << endl;
}

// Trie with prefix substrings
Trie trie;
trie.insert("algorithm"); 
trie.contains("algor"); // true

Example in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

s = "compression" 

# "compre" is a prefix substring
prefix = s[:6]  

# Check if prefix matches
if s.startswith(prefix):
  print(prefix + " is a prefix")

# Trie stores prefixes  
trie = Trie()
trie.insert("compression")
trie.contains("comp") # true

In summary, a prefix substring represents the initial part of a string before any other substrings. Recognizing prefix substrings is useful for many string algorithms and data structures.

A prefix substring refers to the initial part of a string that starts from the beginning and contains contiguous characters of the original string. Prefix substrings are commonly used in various applications like search algorithms, string matching, and data structures such as trie.

For example, the string “apple” has the following prefixes: “a”, “ap”, “app”, “appl”, “apple”.

Solution

Below, you’ll find code implementations for extracting all prefix substrings from a given string in Java, C++, and Python.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public class PrefixSubstring {
    public static void printPrefixes(String str) {
        for (int i = 0; i <= str.length(); i++) {
            String prefix = str.substring(0, i);
            System.out.println(prefix);
        }
    }

    public static void main(String[] args) {
        String str = "apple";
        printPrefixes(str);
    }
}

In Java, the substring method is used to extract the prefix substrings.

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <iostream>
#include <string>

void printPrefixes(const std::string &str) {
    for (size_t i = 0; i <= str.length(); i++) {
        std::string prefix = str.substr(0, i);
        std::cout << prefix << std::endl;
    }
}

int main() {
    std::string str = "apple";
    printPrefixes(str);
    return 0;
}

In C++, the substr method is used to extract the prefix substrings.

Python

1
2
3
4
5
6
7

def print_prefixes(str):
    for i in range(len(str) + 1):
        prefix = str[:i]
        print(prefix)

str = "apple"
print_prefixes(str)

In Python, slicing is used to extract the prefix substrings.

Key Takeaways

• A prefix substring is an initial segment of a string that contains contiguous characters from the start.
• Prefix substrings can be extracted easily using built-in string manipulation methods in different programming languages like substring in Java, substr in C++, and slicing in Python.
• This concept is foundational for several algorithms and data structures related to string processing.