题解 | #寻找连续任务开始位置# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param words string字符串一维数组
     * @return int整型
     */
    public int findLongestSubstring (String s, String[] words) {
        // write code here
        // 将所有的单词拼接成一个模式串
        StringBuilder patternBuilder = new StringBuilder();
        for (String word : words) {
            patternBuilder.append(word);
        }
        String pattern = patternBuilder.toString();

        int n = s.length();
        int m = pattern.length();

        // 计算模式串的next数组
        int[] next = new int[m];
        computeNextArray(pattern, next);

        int i = 0; // 主串的指针
        int j = 0; // 模式串的指针
        int start = -1;
        int maxLength = -1;

        while (i < n) {
            if (s.charAt(i) == pattern.charAt(j)) {
                ++i;
                ++j;
            } else {
                if (j > 0) {
                    j = next[j - 1];
                } else {
                    ++i;
                }
            }

            if (j == m) {
                // 找到了一个匹配的子串
                if (i - j > maxLength) {
                    maxLength = i - j;
                    start = i - m;
                }
                // 继续寻找下一个匹配位置
                j = next[j - 1];
            }
        }

        return start;
    }
    private void computeNextArray(String pattern, int[] next) {
        int m = pattern.length();
        int j = 0; // 模式串的指针

        for (int i = 1; i < m; ++i) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }

            if (pattern.charAt(i) == pattern.charAt(j)) {
                ++j;
            }

            next[i] = j;
        }
    }
}

Java代码。

该题考察的知识点是字符串处理和KMP算法。

使用一个StringBuilder对象patternBuilder来拼接所有的单词，形成模式串pattern。

创建一个整型数组next来保存模式串的next数组。调用computeNextArray方法计算模式串的next数组。

使用两个指针i和j分别表示主串和模式串的指针，以及start和maxLength来记录最长连续子串的起始位置和长度。

在循环中，通过比较当前字符是否匹配，更新指针的位置。如果匹配失败且j大于0，则将j更新为next[j - 1]，否则将i向右移动一位。如果匹配成功，则将i和j都向右移动一位。

当j等于模式串长度时，表示找到了一个匹配的子串。如果该子串的长度大于当前最大长度，则更新最大长度maxLength和起始位置start。

返回最长连续子串的起始位置start。