Analysis and Implementation of Python String Substring Search Algorithms

Problem Background and Algorithm Analysis

In Python string processing, substring search is a fundamental and important operation. The user-provided custom function def find_str(s, char) returned incorrect results when searching for substring "py", revealing critical issues in algorithm design.

Diagnosis of Original Code Issues

The main flaw in the original code lies in searching only for the first character of the substring while ignoring complete substring matching. Detailed analysis follows:

def find_str(s, char):
    index = 0           
    if char in s:
        char = char[0]  # Error: reduces substring to first character
        for ch in s:
            if ch in s:  # Redundant condition
                index += 1
            if ch == char:  # Only matches first character
                return index
    else:
        return -1

When this algorithm searches for "py" in the string "Happy Birthday", it first reduces the substring to 'p', then returns upon finding the first 'p' (position 2), resulting in incorrect output 2 instead of the correct 3.

Improved Algorithm Implementation

Based on the best answer solution, we redesigned a complete substring search algorithm:

def find_str(s, char):
    index = 0
    
    if char in s:
        c = char[0]  # Get first character of substring
        for ch in s:
            if ch == c:  # Find potential match starting position
                # Use slicing to verify complete substring match
                if s[index:index+len(char)] == char:
                    return index
            index += 1
    
    return -1  # Return -1 if not found

Detailed Algorithm Principles

The improved algorithm employs a layered matching strategy:

1. Pre-check: First use char in s to quickly determine substring existence
2. First Character Matching: Traverse string to find matching positions of substring's first character
3. Complete Substring Verification: For each potential starting position, use string slice s[index:index+len(char)] to verify complete match
4. Boundary Handling: Properly handle string boundaries to avoid index out-of-range errors

Testing Verification and Result Analysis

Multiple test cases for the improved algorithm:

print(find_str("Happy birthday", "py"))    # Output: 3
print(find_str("Happy birthday", "rth"))   # Output: 8
print(find_str("Happy birthday", "rh"))    # Output: -1

Test results demonstrate the algorithm correctly handles:

• Basic substring search ("py" at position 3)
• Multi-character substring search ("rth" at position 8)
• Non-existent substring cases ("rh" returns -1)

Comparison with Built-in Methods

While custom algorithms have educational value, Python built-in methods are recommended for practical development:

s = "Happy Birthday"
s2 = "py"
print(s.find(s2))  # Output: 3

Built-in str.find() method offers these advantages:

• Higher execution efficiency (C implementation)
• Better error handling
• More concise code
• Support for additional parameters (start position, end position)

Performance Optimization Considerations

For large-scale string processing, consider these optimization strategies:

1. Early Termination: Return early when remaining string length is less than substring length
2. Character Frequency Analysis: Optimize search order based on character distribution characteristics
3. Algorithm Selection: Choose efficient algorithms like KMP or Boyer-Moore for specific scenarios

Conclusion and Extensions

This paper thoroughly examines the core principles of string matching algorithms through analysis of specific substring search instances. While custom implementations are less efficient than built-in methods, they are significant for understanding algorithmic essence and developing programming thinking. In practical applications, appropriate methods should be selected based on specific requirements, balancing development efficiency with execution performance.