递归求解首尾匹配指定子串的最长子串长度问题求助（需O(n)复杂度）

看来你在实现这个「以指定子串作为首尾的最长子串长度计算」功能时遇到了问题，还要求线性时间复杂度对吧？我来帮你梳理思路，给出能满足需求的解决方案。

首先明确需求：我们要找字符串s中以子串pat同时作为开头和结尾的最长子串长度。核心结论很直接：

• 最长符合条件的子串，必然是从pat第一次出现的起始位置，延伸到pat最后一次出现的结束位置（即最后一次起始索引 + pat的长度）
• 如果pat只出现一次，最长子串就是pat本身，长度为pat.length()
• 如果pat从未出现，返回0
• 要做到O(n)线性时间，绝对不能用递归暴力枚举所有子串——递归很容易导致重复遍历，时间复杂度会飙升到O(n²)

你提到用递归保存了所有可能子串但返回长度不对，大概率是因为递归逻辑没有聚焦在「定位首尾pat的位置」上，反而在枚举子串上消耗了过多资源，既浪费空间又无法保证线性时间。

我们只需要遍历s一次，记录所有pat出现的起始索引，再通过首尾索引计算最长长度即可。这里提供两种实现：基础迭代版（直观易懂）和KMP优化版（长字符串匹配更高效）。

基础迭代实现（O(n+m)时间） #

public class StringPatternMatcher {
    public static int findSubString(String s, String pat) {
        int sLen = s.length();
        int patLen = pat.length();
        
        // 子串比原串长，直接返回0
        if (patLen > sLen) {
            return 0;
        }
        
        int firstOccur = -1;
        int lastOccur = -1;
        
        // 遍历所有可能的起始位置，记录首尾匹配点
        for (int i = 0; i <= sLen - patLen; i++) {
            boolean isMatch = true;
            // 检查当前位置是否匹配pat
            for (int j = 0; j < patLen; j++) {
                if (s.charAt(i + j) != pat.charAt(j)) {
                    isMatch = false;
                    break;
                }
            }
            if (isMatch) {
                if (firstOccur == -1) {
                    firstOccur = i;
                }
                lastOccur = i;
            }
        }
        
        if (firstOccur == -1) {
            return 0; // 未找到匹配
        }
        // 最长长度 = 最后一个pat的结束位置 - 第一个pat的起始位置
        return (lastOccur + patLen) - firstOccur;
    }

    public static void main(String[] args) {
        // 测试用例验证
        System.out.println(findSubString("abcxyzabc123abc", "abc")); // 输出15
        System.out.println(findSubString("ababa", "aba")); // 输出5
        System.out.println(findSubString("test", "test")); // 输出4
        System.out.println(findSubString("hello", "world")); // 输出0
    }
}

KMP优化实现（严格O(n+m)时间） #

如果pat或s很长，基础版的内层匹配可能会有重复比较，用KMP算法的前缀函数可以避免这个问题，进一步优化效率：

public class StringPatternMatcher {
    // 计算KMP算法的前缀函数（部分匹配表）
    private static int[] computePrefixFunction(String pat) {
        int m = pat.length();
        int[] lps = new int[m];
        int len = 0; // 最长相等前后缀长度
        
        for (int i = 1; i < m; ) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static int findSubString(String s, String pat) {
        int sLen = s.length();
        int patLen = pat.length();
        
        if (patLen > sLen) {
            return 0;
        }
        
        int[] lps = computePrefixFunction(pat);
        int firstOccur = -1;
        int lastOccur = -1;
        int i = 0; // s的遍历指针
        int j = 0; // pat的遍历指针
        
        while (i < sLen) {
            if (pat.charAt(j) == s.charAt(i)) {
                i++;
                j++;
            }
            if (j == patLen) {
                // 找到匹配，记录位置
                int currentPos = i - j;
                if (firstOccur == -1) {
                    firstOccur = currentPos;
                }
                lastOccur = currentPos;
                j = lps[j - 1];
            } else if (i < sLen && pat.charAt(j) != s.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        if (firstOccur == -1) {
            return 0;
        }
        return (lastOccur + patLen) - firstOccur;
    }

    public static void main(String[] args) {
        System.out.println(findSubString("abcxyzabc123abc", "abc")); // 15
        System.out.println(findSubString("ababa", "aba")); // 5
        System.out.println(findSubString("test", "test")); //4
        System.out.println(findSubString("hello", "world")); //0
    }
}

如果一定要用递归实现，需要避免重复遍历——比如递归遍历s时只记录首尾pat的位置，而不是枚举所有子串。但递归会占用额外的调用栈空间，且效率不如迭代，因此更推荐上面的线性时间迭代方案。

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