题解 | #牛群的信息传递#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param message string字符串
     * @param keyword string字符串
     * @return int整型
     */
  /**
  方法1：KMP算法，但貌似在这种简单题，反而耗时久，KMP适合长文本，重复文本较多的情况
  */
    public int findKeyword (String message, String keyword) {
        int messageLength = message.length();
        int keywordLength = keyword.length();

        int[] lps = calculateLPS(keyword);
        int i = 0;
        int j = 0;

        while (i < messageLength) {
            if (message.charAt(i) == keyword.charAt(j)) {
                i++;
                j++;

                if (j == keywordLength) {
                    return i - j; // 匹配成功，返回起始位置下标
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }

        return -1; // 未找到关键词
    }
    private static int[] calculateLPS(String keyword) {
        int length = keyword.length();
        int[] lps = new int[length];
        int i = 1;
        int j = 0;

        while (i < length) {
            if (keyword.charAt(i) == keyword.charAt(j)) {
                j++;
                lps[i] = j;
                i++;
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }
  /**
  方法二： 线性探测法，貌似本题是最快的 13ms， Java语言
  */
   public int findKeyword (String message, String keyword) {
          int messageLength = message.length();
        int keywordLength = keyword.length();
        
        for (int i = 0; i <= messageLength - keywordLength; i++) {
            int j;
            for (j = 0; j < keywordLength; j++) {
                if (message.charAt(i + j) != keyword.charAt(j)) {
                    break;
                }
            }
            if (j == keywordLength) {
                return i; // 匹配成功，返回起始位置下标
            }
        }
        
        return -1; // 未找到关键词
    }
}

本题知识点分析:

1.KMP算法

2.线性探测法

3.字符串遍历

本题解题思路分析：

1.不建议直接用函数库偷懒,用indexof,split完全丧失了出题的意义，一般题目都会说不用标准库函数去自己写

2.KMP

3.线性探测（最快）直接遍历然后取字符，直到全部字符判断相等，返回索引即可

本题使用编程语言Java