【代码随想录09】28. 找出字符串中第一个匹配项的下标 459. 重复的子字符串

本文主要是介绍【代码随想录09】28. 找出字符串中第一个匹配项的下标 459. 重复的子字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

28. 找出字符串中第一个匹配项的下标

题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

参考代码

class Solution {public int strStr(String haystack, String needle) {int m = needle.length();// 当 needle 是空字符串时我们应当返回 0if (m == 0) {return 0;}int n = haystack.length();if (n < m) {return -1;}int i = 0;int j = 0;while (i < n - m + 1) {// 找到首字母相等while (i < n && haystack.charAt(i) != needle.charAt(j)) {i++;}if (i == n) {// 没有首字母相等的return -1;}// 遍历后续字符，判断是否相等i++;j++;while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {i++;j++;}if (j == m) {// 找到return i - j;} else {// 未找到i -= j - 1;j = 0;}}return -1;}
}

459.重复的子字符串

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

参考代码

class Solution {public boolean repeatedSubstringPattern(String s) {if (s.equals("")) return false;int len = s.length();// 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了s = " " + s;char[] chars = s.toCharArray();int[] next = new int[len + 1];// 构造 next 数组过程，j从0开始(空格)，i从2开始for (int i = 2, j = 0; i <= len; i++) {// 匹配不成功，j回到前一位置 next 数组所对应的值while (j > 0 && chars[i] != chars[j + 1]) j = next[j];// 匹配成功，j往后移if (chars[i] == chars[j + 1]) j++;// 更新 next 数组的值next[i] = j;}// 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值if (next[len] > 0 && len % (len - next[len]) == 0) {return true;}return false;}
}