Searching Algorithm场景下Java子串查找方法运行异常排查

你实现的朴素字符串查找算法存在多处逻辑漏洞，无法正确完成「判断text2是否为text1子串」的需求，原代码如下：

static boolean findeText(String text1, String text2) {

    char c1[] = text1.toCharArray();
    char c2[] = text2.toCharArray();
    boolean b = false;
    for (int i = 0; i <= c1.length - c2.length; i++) {
        for (int j = 0, h = i; j <= c2.length; j++, h++) {
            if (i == c2.length) {
                return true;
            }
            if (c1[h] != c2[j]) {
                b = false;
                break;
            }
        }
    }
    return b;
}

具体错误点 #

• 内层循环边界越界：内层循环终止条件写为j <= c2.length，由于Java数组下标从0开始计数，字符数组c2的合法下标范围是0 ~ c2.length-1，当j等于c2.length时访问c2[j]会直接抛出数组下标越界异常。
• 匹配成功判断逻辑完全错误：原代码以i == c2.length作为匹配成功的判定条件，其中i是text1上的匹配起始偏移量，和text2的长度没有对应关系，根本无法代表子串完全匹配。
• 匹配标记位从未正确赋值：变量b初始值为false，全流程中只有将其重置为false的逻辑，从未在匹配成功时将其设为true，即使真的匹配到子串最终也会返回false。
• 缺失边界场景处理：没有处理text2为空串、text2长度大于text1的特殊场景，会出现不符合预期的行为。

修正后代码 #

static boolean findeText(String text1, String text2) {
    // 前置边界处理
    if (text2.length() == 0) return true;
    if (text2.length() > text1.length()) return false;

    char[] c1 = text1.toCharArray();
    char[] c2 = text2.toCharArray();

    for (int i = 0; i <= c1.length - c2.length; i++) {
        int j;
        // 逐字符匹配，修正循环边界避免越界
        for (j = 0; j < c2.length; j++) {
            if (c1[i + j] != c2[j]) {
                break;
            }
        }
        // 内层循环完整走完，说明所有字符匹配成功
        if (j == c2.length) {
            return true;
        }
    }
    return false;
}

内容的提问来源于stack exchange，提问作者mohammad amin jeddi