代码随想录算法训练营第九天|28.实现strStr()、459.重复的子字符串

本文主要是介绍代码随想录算法训练营第九天|28.实现strStr()、459.重复的子字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录算法训练营第九天|28.实现strStr()、459.重复的子字符串

28.实现strStr()；找出字符串第一个匹配项的下标

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

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

题解：解决字符串匹配问题：KMP算法，当遇到不匹配的字符时，回退到不匹配字符的下标的前一位对应位置的字符。这个算法的核心是求出next数组。

求next数组的步骤：

初始化next数组（next[0]=0），第一个字符不能再回退了。
处理字符相同的情况（相同就j++）
处理字符不同的情况（while循环，回退到字符与目前字符相同，直到回到下标为0）
更新next数组

next数组求出来后，两个字符串的匹配过程与求解next数组的类似。

代码：

class Solution {public int strStr(String haystack, String needle) {if(needle.length() == 0) return 0;//next数组int [] next=new int[needle.length()];//填充next数组getNext(next,needle);//开始比对字符串int j=0;for(int i=0;i<haystack.length();i++){while(j>0 && needle.charAt(j)!= haystack.charAt(i)){j=next[j-1];}if(haystack.charAt(i)==needle.charAt(j)){j++;}if(j==needle.length()){return i-needle.length()+1;}}return -1;}public void getNext(int [] next,String s){int j=0;next[0]=0;for(int i=1;i<s.length();i++){//如果字符不相等,j要一直回退while(j>0 && s.charAt(j)!=s.charAt(i)){j=next[j-1];}if(s.charAt(i)==s.charAt(j)){j++;}next[i]=j;}}
}

459.重复的子字符串

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

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

题解：方法一，算是一个技巧吧。判断这个字符串是否由他的字串重复构成，那么将这个字串重复一遍，去掉首尾字符，如果经过处理后的字符串中含有这个字符串，那么就由重复的字符串构成。

我没有更好删除首尾字符的方法，所以用了StringBuilder来将首尾字符替换成空格。

代码：

class Solution {public boolean repeatedSubstringPattern(String s) {StringBuilder sb=new StringBuilder(s+s);sb.setCharAt(0,' ');sb.setCharAt(sb.length()-1,' ');String ss=sb.toString();if(ss.contains(s)){return true;}return false;}
}