Horspool算法匹配首个结果即停止，求修改实现全文本搜索

I spot the issue immediately—your current code bails out as soon as it finds the first match with return index, which cuts off the search before it can check the rest of the haystack. Let's tweak this so the algorithm keeps going and captures all matching positions, or at least continues searching if that's what you need.

What's Causing the Halt? #

The core problem is your method returns a single int and exits the moment it finds a match. To scan the entire text, we need to:

• Change the return type to hold multiple match indices (or adjust logic to keep searching even after finding a hit)
• Remove the early return when a match is found
• Make sure we correctly advance the search index after a match to avoid infinite loops

Modified Code (Collects All Matches) #

Here's the adjusted version that finds every starting position where the needle appears in the haystack:

public static class BoyerMooreHorspool {
    public static List<int> FindAllMatches(string haystack, string needle) {
        var matches = new List<int>();
        
        // Handle edge cases first
        if (string.IsNullOrEmpty(needle) || needle.Length > haystack.Length) {
            return matches;
        }
        if (needle.Except(haystack).Any()) {
            return matches;
        }

        // Build the bad match table
        Dictionary<char, int> badMatchTable = new Dictionary<char, int>();
        foreach (char c in haystack) {
            if (!badMatchTable.ContainsKey(c)) {
                badMatchTable[c] = needle.Length;
            }
        }
        for (int i = 0; i < needle.Length - 1; i++) {
            badMatchTable[needle[i]] = needle.Length - i - 1;
        }

        int index = 0;
        while (index <= haystack.Length - needle.Length) {
            bool match = true;
            for (int i = needle.Length - 1; i >= 0; i--) {
                if (needle[i] != haystack[index + i]) {
                    match = false;
                    // Move index using the bad match rule
                    index += badMatchTable[haystack[index + needle.Length - 1]];
                    break; // Exit inner loop early once mismatch is found (saves time)
                }
            }

            if (match) {
                matches.Add(index);
                // Don't stop here—advance index to look for next matches
                // Use bad match table for efficiency, or move by 1 if you prefer
                index += badMatchTable.ContainsKey(haystack[index + needle.Length - 1]) 
                    ? badMatchTable[haystack[index + needle.Length - 1]] 
                    : needle.Length;
            }
            // Prevent infinite loop if we reach the end without a mismatch
            else if (index >= haystack.Length - needle.Length) {
                break;
            }
        }

        return matches;
    }
}

Key Changes Breakdown: #

• Return Type: Switched from int to List<int> to store all matching starting indices
• No Early Exit: Instead of returning immediately when a match is found, we add the index to our list and keep searching
• Post-Match Index Advancement: After a match, we still use the bad match table to skip unnecessary checks (this keeps the algorithm efficient)
• Inner Loop Optimization: Added a break after finding a mismatch to avoid wasting cycles checking remaining characters
• Robust Edge Cases: Updated initial checks to handle empty strings gracefully

How to Use It: #

Call the method like this to get all matches:

string haystack = "ababcabcabx";
string needle = "abc";
List<int> matches = BoyerMooreHorspool.FindAllMatches(haystack, needle);
// Returns [2, 5] since "abc" starts at positions 2 and 5

If you still want a way to get just the first match, you could add an overload that returns matches.FirstOrDefault(-1), but this version solves your core problem of searching the entire text.

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