做视频网站服务器要求,织梦模板可以在wordpress用,关于小说网站的一些建设流程,漫蛙漫画网页版链接目录 459、重复的子字符串题目描述暴力匹配思路代码 字符串匹配思路代码与暴力匹配的不同 KMP解法思路代码KMP算法的核心和用途 459、重复的子字符串
题目描述
给定一个非空的字符串 s #xff0c;检查是否可以通过由它的一个子串重复多次构成。
暴力匹配
思路
推理 如果… 目录 459、重复的子字符串题目描述暴力匹配思路代码 字符串匹配思路代码与暴力匹配的不同 KMP解法思路代码KMP算法的核心和用途 459、重复的子字符串
题目描述
给定一个非空的字符串 s 检查是否可以通过由它的一个子串重复多次构成。
暴力匹配
思路
推理 如果存在这样的子串那么这个子串一定是s的前缀。s的长度n一定是子串长度n1的整数倍s中的元素s[i]与往前移n1的元素s[i-n1]相同 方法 因此从小到大枚举出所有可能的子串长度n1再对这个子串进行上述的判断即可。 优化这个子串至少要在s中重复一次所以n1的范围为[1,n/2]。 代码
class Solution {
public:bool repeatedSubstringPattern(string s) {int n s.size();//i代表子串的长度应从1开始for (int i 1; i n / 2; i) {//判断该子串是否为目标子串if (n % i 0) {bool match true;//判断之后的字符往前移子串长度i之后是否相等//从子串之后开始遍历整个字符串for (int j i; j n; j) {if (s[j] ! s[j - i]) {match false;break;} }if (match) return true;}}return false;}
};时间复杂度O(n2)枚举子串的时间复杂度为O(n)遍历判断子串的时间复杂度为O(n)。 空间复杂度O(1) 字符串匹配
思路
如果s满足题目要求那么s具有以下性质 设s的长度为n子串长度s1为n1.可以把s写成n/n1个子串s1排列的形式 s——s1s1s1s1…那么把第一个s1移到最后面字符串s不变 根据性质可以证明 因为1 n1 n那么把两个字符串s连在一起得到S把连在一起后的字符串S移除前后第一个元素这时字符串s一定是拼接串S的子串 根据证明结果得到方法 拼接两个字符串s移除第一个和最后一个字符如果s是其中的子串则满足题目要求 代码
class Solution {
public:bool repeatedSubstringPattern(string s) {return (s s).find(s, 1) ! s.size();}
};与暴力匹配的不同
通过推理得到一种满足要求是的情况只要针对这个情况进行判断即可。
KMP解法
思路
假设推理 假设这个文本串由重复子串组成找到这个文本串的最长公共前后缀文本串切割掉最长公共前后缀剩下的就是重复子串 可用的结论 设文本串s由n个长度为x的子串组成则文本串全长为nx。最长公共前后缀由m个长度为x的子串组成长度为mx。则重复子串长度为(n-m)x。n-m1当全长nx对重复子串长度(n-m)x取余等于0时(即nx % (n-m)x 0 or nx % x 0)证明(n-m)x代表的子串为重复子字符串。 方法 求出next数组next数组长度为len使用next数组存储文本串中最长公共前后缀的长度next[len - 1]如果 len % (len -next[len - 1]) 0则表明存在重复子字符串 代码
class Solution {
public://得出next数组void getNext(int* next, string s) {//初始化int j 0;//前缀末尾从0开始next[0] j;//从长度为2的子串开始求最长公共前后缀长度for (int i 1; i s.size(); i) {//前后缀末尾不匹配时while (j 0 s[i] ! s[j]) j next[j - 1];//j回退//前后缀末尾匹配时if (s[i] s[j]) {j;//j(和i)往后移一位}next[i] j;//下标j为当前子串(末尾下标为i)的最长公共前后缀长度}}bool repeatedSubstringPattern(string s) {int next[s.size()];//创建长度为字符串长度的前缀表getNext(next[0], s);//使用最长公共前后缀长度判断是否由重复的子字符串组成int len s.size();//next[len - 1] 0时证明整个字符串最长公共前后缀长度为0//根据推理得出的结论:当len % (len - next[len-1]) 0 时证明(有重复的子字符串/最后一段字符串为重复子字符串)if (next[len - 1] ! 0 len % (len - next[len-1]) 0) return true;return false;}
};时间复杂度O(n)得到前缀表时遍历字符串需要O(n)判断重复子字符串只用了固定的操作数。 空间复杂度O(n)需要前缀表存储字符串的所有前缀子串(包括它自身)的最长公共前后缀长度。 KMP算法的核心和用途
核心 前缀表next其中存储了字符串的最长公共前后缀长度。匹配时使用前缀表记录的最长公共前后缀长度来进行回退。总结存储字符串的最长公共前后缀长度的前缀表、回退思想。 用途 使用前缀表回退查找子字符串。使用前缀表中记录的最长公共前后缀长度来进行一些数字上的判断。
