Case Insensitive Search In C++

Conducting a case-insensitive search in C++ necessitates standardizing the case of characters (either to upper or lower case) prior to comparison. This guarantees that variations in letter casing do not impact the outcome.

When conducting a search that is case-sensitive, the comparison takes into account the precise casing of letters (for example, 'A' is not equal to 'a'). Conversely, in a case-insensitive search, the letter case is disregarded, treating 'A' and 'a' as identical.

Explanation with Example

Suppose you possess a reference string and a query term:

• ✅ Reference string: "Greetings Earth"
• ✅ Query term: "planet"

To perform a case-insensitive search:

• ✅ Change both "Hello World" and "world" to lowercase:
• ✅ "hello world"

Utilize std::string::find method to locate the lowercase search term within the lowercase source string.

Approach 1: Simple Approach

Example:

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype> // For ::tolower
// Function to perform a case-insensitive search
bool caseInsensitiveSearch(const std::string& source, const std::string& target) {
    // Convert both strings to lowercase
    std::string source_lower = source;
    std::string target_lower = target;
    std::transform(source_lower.begin(), source_lower.end(), source_lower.begin(), ::tolower);
    std::transform(target_lower.begin(), target_lower.end(), target_lower.begin(), ::tolower);
    // Use std::string::find to search for the target in the source
    return source_lower.find(target_lower) != std::string::npos;
}
int main() {
    std::string source, target;
    // Input source string and search term
    std::cout << "Enter the source string: ";
    std::getline(std::cin, source);
    std::cout << "Enter the search term: ";
    std::getline(std::cin, target);
    // Perform case-insensitive search
    if (caseInsensitiveSearch(source, target)) {
        std::cout << "The search term \"" << target << "\" was found in the source string.\n";
    } else {
        std::cout << "The search term \"" << target << "\" was not found in the source string.\n";
    }
    return 0;
}

Output:

Enter the source string: Hello World
Enter the search term: WORLD
The search term "WORLD" was not found in the source string.

Explanation:

Step 1: Accept Input from the User

The process begins with prompting the user to input two strings:

• ✅ Initial string: This longer text will be the target of our search.
• ✅ Target term: This specific text is what we aim to find within the initial string.

Both inputs are gathered using a technique that permits spaces within the text, offering adaptability in the input process.

Step 2: Create a Function for the Search Logic

To enhance reusability and modularity, the search algorithm itself is encapsulated within a distinct function. This particular function requires two strings as arguments:

• ✅ The source string serving as the search space.
• ✅ The target string, which represents the term being sought after.

This division of responsibilities guarantees that the search algorithm can be repurposed in different sections of a program when necessary.

Step 3: Normalize Both Strings

To enable case-insensitive search functionality, it is essential to disregard the letter case. This means that variations like "World" and "world" should be considered identical during the search process. In order to implement this feature:

Replicate the origin and query strings to maintain their initial formats.

• ✅ each character is converted to lowercase using a function designed for this purpose.
• ✅ this guarantees that both strings have consistent casing, simplifying comparisons.

Step 4: Perform the Search

After transforming both strings to lowercase:

• ✅ The software hunts for the desired string in the original string using a conventional searching technique. This process verifies if the string of characters in the desired string corresponds to any segment of the original string.
• ✅ The searching approach employed will provide the index of the initial match upon locating the desired string. In case of no match, it will signify an unsuccessful search with a distinct value.

Step 5: Return the Search Result

The function proceeds to check if the specified string has been located:

If the indicated string is present within the original string, the function will yield a true result.

In cases where the specified string cannot be located, the function will output false.

Step 6: Display the Result to the User

Back in the main part of the program:

The function is invoked with the provided strings, and the output is verified.

Depending on the outcome:

• ✅ In the case of true, a notification is displayed to inform that the search term has been located within the source string.
• ✅ In the case of false, a notification is displayed to inform that the search term was not found.

Complexity Analysis:

Time Complexity

Duplicating Strings:

• ✅ Replicating the source and destination strings requires O(n) and O(m) time complexity, respectively. Here, n represents the size of the original string, while m denotes the length of the target term.

Converting to lowercase:

• ✅ Switching both strings to lowercase requires O(n) for the original string and O(m) for the query term.

Searching for a Substring:

When utilizing std::string::find, the worst-case time complexity is O(n⋅m) due to the potential comparison of each character in the source string with each character in the search term.

Total Time Complexity:

Combining these, the total time complexity becomes O(n+m+n⋅m). Typically, the O(n⋅m) component is the most dominant in the majority of scenarios.

Space Complexity

Two additional strings (for the lowercase iterations of the original and target terms) necessitate O(n) and O(m) memory, correspondingly.

Temporary Variables:

The temporary storage utilized for character conversion has a minor impact on space requirements and does not notably affect the space complexity.

Total Space Complexity:

The space complexity amounts to O(n+m) as a result of allocating memory for the modified strings.

Approach 2: Direct Case-Insensitive Comparison

This approach involves evaluating each character in the source string against the corresponding character in the target string, converting only those characters being compared to the same case (either lowercase or uppercase) as needed. This method eliminates the requirement for transforming the entire strings and proves to be a space-efficient solution.

Program:

#include <iostream>
#include <string>
#include <cctype> // For ::tolower
// Function to perform a case-insensitive search
bool caseInsensitiveSearch(const std::string& source, const std::string& target) {
    int n = source.length();
    int m = target.length();
    // Loop through the source string, comparing substrings of length m
    for (int i = 0; i <= n - m; ++i) {
        bool match = true;
        // Compare each character of the substring with the target
        for (int j = 0; j < m; ++j) {
            // Compare characters in a case-insensitive way
            if (std::tolower(source[i + j]) != std::tolower(target[j])) {
                match = false;
                break;
            }
        }
        if (match) {
            return true; // Found a match
        }
    }
    return false; // No match found
}
int main() {
    std::string source, target;
    // Input source string and search term
    std::cout << "Enter the source string: ";
    std::getline(std::cin, source);
    std::cout << "Enter the search term: ";
    std::getline(std::cin, target);
    // Perform case-insensitive search
    if (caseInsensitiveSearch(source, target)) {
        std::cout << "The search term \"" << target << "\" was found in the source string.\n";
    } else {
        std::cout << "The search term \"" << target << "\" was not found in the source string.\n";
    }
    return 0;
}

Output:

Enter the source string: Hello world
Enter the search term HELLO
The search term "HELLO" was found in the source string.

Explanation:

Step 1: Accepting Input

The software initiates by prompting the user to enter two strings:

This is the text where we are looking for the specified string.

Search term: This specific substring is the one we are seeking within the original string.

These inputs are gathered using std::getline, enabling users to enter multi-word strings, including spaces.

Step 2: Starting the Search

The fundamental logic for conducting the search is contained within a function that requires two inputs:

• ✅ The original text (comprising the larger body of content).
• ✅ The specific term (the portion of text we aim to find within the original content).

The objective of this function is to determine whether the target string is present within the source string. It will return true if the target string is found, and false if it is not.

Step 3: Iterating Over the Source String

The subsequent phase includes looping through the source string. The concept is to examine each potential starting position for the search term within the source string and then contrast the characters.

• ✅ At every index in the source string, we will evaluate the substring matching the search term's length.
• ✅ By utilizing the loop, we guarantee that we exclusively assess legitimate positions where the search term can be accommodated within the source string.

Step 4: Comparing Each Substring

For every possible initial index in the input string, the software evaluates the segment (starting from that index) against the specified keyword. The assessment involves a meticulous examination of each character.

However, in order to achieve case insensitivity, we do not directly match the characters. Rather, we convert both the characters (from the original string and the search term) to a consistent case (either all lowercase or all uppercase) prior to comparison. This guarantees that characters such as 'A' and 'a' or 'b' and 'B' are considered equivalent.

Step 5: Checking for a Match

If all characters in the given substring match the corresponding characters in the search term (without considering case), it signifies that the search term has been located within the original string. Consequently, the function promptly returns true to signify a successful match.

If a single character doesn't match, even in a case-insensitive manner, the function will consider the comparison unsuccessful and proceed to search from the next potential starting position in the source string.

Step 6: Handling Non-Matches

If the program exhausts all potential starting points in the source string without encountering a match, it will result in a false return. This indicates the absence of the target string within the source string.

Step 7: Output the Result

Finally, the outcome of the search operation (whether the desired item was located or not) is exhibited to the user within the primary section of the application:

If the function returns true, a notification of success is shown, confirming the presence of the search term.

Conversely, if false is returned, an error message is displayed conveying that the search term was not located.

Complexity Analysis:

Time Complexity:

• ✅ Looping through the Source String: The program loops through the source string, checking each possible starting position for the search term. This gives O(n), where n is the length of the source string.
• ✅ Character Comparisons: For each starting position, we compare each character of the source substring with the target string. This comparison takes O(m), where m is the length of the target string.
• ✅ The worst-case time complexity is O(n⋅m), as in the worst case, we might compare each character in the source string to each character in the target string.

Space Complexity:

• ✅ Minimal Space: The process relies on a small number of variables to keep track of the string's position and conduct comparisons. It does not form new data structures such as arrays or strings.
• ✅ The space complexity remains O(1) as the space requirement stays constant regardless of the input's scale.

Advantages:

Space Optimization:

• ✅ This method excels in space efficiency by eliminating the need for generating extra strings or data structures. It relies solely on a small number of variables for indexing and comparison, resulting in a constant space complexity of O(1).

Unlike alternative techniques that change the entirety of the original and destination strings to lowercase or uppercase, this method conducts case-insensitive checks dynamically. This eliminates the necessity to generate duplicates of the strings, resulting in time and space efficiency.

Straightforward and Clear:

• ✅ The method is uncomplicated and simple to execute. It directly compares characters and maintains case insensitivity by converting characters as needed, eliminating the need for complex logic.

Efficient with Small Inputs:

When dealing with shorter strings or brief search terms, this method can prove to be highly effective as it circumvents the need to generate additional string copies or perform extensive transformations.

Easy to Grasp and Apply:

• ✅ This technique is straightforward to comprehend and execute, which makes it an excellent option for novices or situations requiring a rapid resolution. It does not entail intricate ideas, only fundamental loops and string manipulations, rendering it accessible to individuals studying C++.

Disadvantages:

Worst-Case Time Complexity:

In the worst-case scenario, the time complexity of O(n⋅m) can lead to inefficiencies when dealing with substantial input sizes. When working with extensive source strings and search terms, this method may not offer the most efficient solution.

Performing case conversions repeatedly can become redundant as each comparison involves converting characters to lowercase or uppercase. This redundancy is more noticeable when dealing with short target strings or lengthy source strings, leading to increased processing overhead when compared to approaches that preprocess the strings just once.

Limited Enhancement for Extensive Inputs:

This method does not incorporate sophisticated optimization methods such as Boyer-Moore or Knuth-Morris-Pratt, which have the potential to decrease time complexity significantly in real-world situations. Hence, when dealing with substantial datasets or repeated searches, this technique might not demonstrate efficient scalability.

Not Suitable for Parallelization:

• ✅ The searching procedure is fundamentally sequential, which makes parallelization challenging. This could pose a constraint for scenarios requiring processing of extensive texts or frequent searches.

While this technique is effective for conducting case-insensitive searches, it may not address more intricate scenarios like locale-specific case folding or various character encodings (e.g., special symbols or accented characters). To accommodate diverse languages or character sets, further enhancements may be necessary for this approach in advanced text processing.