字符串中子串出现次数统计及无序子串查找技术问询

Hey folks, let's tackle these two common string substring problems with clear explanations and working code examples:

1. Count Occurrences of a Specific Ordered Substring #

This problem asks us to count how many times a given target substring appears in order within a longer input string.

Example #

• Input string: AXBHAAGHXAXBH
• Target substring: AXBH
• Expected output: 2 (the target appears at the start and end of the input string)

C++ Implementation #

We can solve this using a loop with std::string::find(), which lets us repeatedly search for the target starting from a specific position:

#include <string>
#include <iostream>

int main() {
    int occurrences = 0;
    std::string::size_type pos = 0;
    std::string inputz = "AXBHAAGHXAXBH";
    std::string target = "AXBH";

    while ((pos = inputz.find(target, pos)) != std::string::npos) {
        ++occurrences;
        // Move past the current match to avoid re-counting the same substring
        pos += target.length();
    }

    std::cout << "Number of occurrences: " << occurrences << std::endl;
    return 0;
}

Notes #

• The code outputs Number of occurrences: 2, which matches the example.
• If you need to count overlapping substrings (e.g., counting AA in AAAA should return 3 instead of 1), just change pos += target.length(); to pos += 1;.

2. Unordered Substring Search Problem #

Unordered substring search refers to scenarios where we care about the presence of characters (not their order) in a substring. Common use cases include:

• Checking if any substring contains all characters from a target set
• Finding the shortest substring that includes all target characters
• Counting all substrings that contain every character from the target set

Example Scenario: Find the Shortest Substring Containing All Target Characters #

Let's use the sliding window technique—an efficient approach for this type of problem—to find the shortest substring in aabbcc that includes both a and c (our target characters).

C++ Implementation #

#include <string>
#include <unordered_map>
#include <climits>
#include <iostream>

std::string findShortestUnorderedSubstring(const std::string& s, const std::string& target) {
    std::unordered_map<char, int> targetCount, windowCount;
    // Initialize count of each character in the target
    for (char c : target) {
        targetCount[c]++;
    }

    int left = 0, right = 0;
    int matched = 0; // Tracks how many unique target characters are fully matched in the window
    int minLength = INT_MAX;
    int startIdx = 0; // Stores the start index of the shortest valid substring

    while (right < s.size()) {
        char cRight = s[right];
        windowCount[cRight]++;

        // If current character is in target and window has enough of it, increment match count
        if (targetCount.count(cRight) && windowCount[cRight] == targetCount[cRight]) {
            matched++;
        }

        // Shrink the window from the left as much as possible while all targets are matched
        while (matched == targetCount.size()) {
            // Update the shortest substring if current window is smaller
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                startIdx = left;
            }

            char cLeft = s[left];
            windowCount[cLeft]--;

            // If removing the left character breaks the match, decrement matched count
            if (targetCount.count(cLeft) && windowCount[cLeft] < targetCount[cLeft]) {
                matched--;
            }

            left++;
        }

        right++;
    }

    // Return empty string if no valid substring found, else return the shortest one
    return minLength == INT_MAX ? "" : s.substr(startIdx, minLength);
}

int main() {
    std::string input = "aabbcc";
    std::string target = "ac";
    std::string result = findShortestUnorderedSubstring(input, target);
    std::cout << "Shortest substring containing all target characters: " << result << std::endl;
    // Output will be a valid 4-character substring like "abbc" or "abbc"
    return 0;
}

Key Takeaway #

The sliding window method runs in O(n) time (where n is the length of the input string), making it ideal for large datasets. For other unordered substring tasks (like counting valid substrings), you can adapt this logic by adjusting how you track and count valid windows.

内容的提问来源于stack exchange，提问作者Alex Ham