Java String Substring Matching Algorithms: Infinite Loop Analysis and Solutions

Problem Background and Phenomenon Analysis

In Java string processing, using the indexOf method to count substring occurrences is a common requirement. The original code contains a critical flaw: the lastIndex += findStr.length(); statement is placed outside the conditional check, causing the program to continue incrementing the index even when indexOf returns -1 (indicating no match found). This prevents lastIndex from remaining at -1, resulting in an infinite loop.

Core Problem Analysis

Java's String.indexOf(String str, int fromIndex) method searches for a substring starting from the specified index, returning the position of the first occurrence or -1 if not found. The logical flaw in the original code lies in executing lastIndex += findStr.length() regardless of whether a match is found, which breaks the loop termination condition.

The correct logic should be: only update the search starting position when a successful match is found. The fixed code moves the index update operation inside the conditional block:

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
int lastIndex = 0;
int count = 0;

while(lastIndex != -1){
    lastIndex = str.indexOf(findStr, lastIndex);
    
    if(lastIndex != -1){
        count++;
        lastIndex += findStr.length();
    }
}
System.out.println(count);

Algorithm Implementation Details

The workflow of this algorithm can be broken down into the following steps:

1. Initialize lastIndex to 0, starting the search from the beginning of the string
2. Call indexOf(findStr, lastIndex) within the loop to find the next matching position
3. If a match is found (return value not equal to -1), increment the counter and move the search starting position after the matched substring
4. If no match is found, the loop condition lastIndex != -1 is no longer satisfied, and the loop terminates

This implementation has a time complexity of O(n), where n is the length of the main string, as each character is checked at most once.

Alternative Approaches Comparison

Beyond the basic indexOf method, Java provides several other ways to count substring occurrences:

Using Apache Commons Lang Library

StringUtils.countMatches offers a concise API:

System.out.println(StringUtils.countMatches(str, findStr));

This approach provides clean code but requires external dependencies.

String Split-Based Method

Utilizing the split method:

System.out.println(str.split(findStr, -1).length - 1);

This method is clever but may incur performance overhead with large strings due to array creation.

Regular Expression Approach

Using Pattern and Matcher:

Pattern p = Pattern.compile(findStr);
Matcher m = p.matcher(str);
int count = 0;
while (m.find()) {
    count++;
}
System.out.println(count);

This method is powerful for complex matching patterns but may be overkill for simple substring matching.

String Replacement Method

Calculating occurrences through string length difference:

public static int count(String str, String target) {
    return (str.length() - str.replace(target, "").length()) / target.length();
}

This method is mathematically elegant but creates new string objects, making it unsuitable for large-scale data processing.

Performance and Applicability Analysis

For simple substring matching tasks, the fixed indexOf method is generally the best choice because:

• No external dependencies required
• High memory efficiency, no additional string or array objects created
• Optimal time complexity
• Good code readability, easy to understand and maintain

When choosing a specific implementation, consider project requirements: if Apache Commons Lang is already used, StringUtils.countMatches might be preferable; for complex pattern matching, the regex approach is more suitable.

Best Practices Recommendations

When implementing substring counting functionality, consider:

1. Carefully handle boundary conditions, especially loop termination
2. Account for empty strings and null values
3. Choose optimal algorithm implementations for performance-critical scenarios
4. Write unit tests covering various edge cases
5. Maintain consistent coding style in team projects

By understanding these core concepts and implementation details, developers can avoid common pitfalls and write robust, efficient string processing code.