Leetcode 459.重复的子字符串
重复的子字符串
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
复习一下KMP算法
KMP的主要思想是利用字符串自身的前缀后缀的对称性,来构建next数组,从而实现用接近O(N)的时间复杂度完成字符串的匹配
对于一个字符串str,next[j] = k 表示满足str[0...k-1] = str[j-k...j-1]的最大的k,即对于子串str[0...j-1],前k个字母等于后k个字母
现在求解str的next数组:
初始化:next[0] = -1
那么在知道了next[j]的情况下,如何递推地求出next[j+1]呢?分两种情况(令k=next[j]):
1、如果str[j]==str[k],则next[j+1] = k+1
如下图所示,对于str[0...j-1],前k个字母等于后k个字母(两个绿色部分相等),然后str[k]刚好是前k个字母的下一个字母(第一个红色)
如果str[j]==str[k],说明对于str[0...j],前k+1个字母等于后k+1个字母(绿色+红色=绿色+红色),即等于next[j]+1(绿色长度为k,红色长度为1)
2、如果str[j]!=str[k],则k=next[k],然后继续循环(回到1),直到k=-1
因为str[j]!=str[k](下图中紫色和红色不相等),所以前k+1个字母不再等于后k+1个字母了
但是由于前k个字母还是等于后k个字母(图中两个黑色虚线框住部分),所以对于任意的k'<k,str[k-k'...k-1]=str[j-k'...j-1](图中第二个和最后一个绿色相等)
而next[k]表示str[0...k-1]内部的对称情况,所以令k'=next[k],则对于str[0...k-1],前k'个字母等于后k'个字母(图中第一个和第二个绿色相等)
由于图中第二个绿色始终=第四个绿色,所以第一个绿色等于第四个绿色
因此将k=next[l]继续带入循环,回到判断1:
如果str[k']=str[j],则满足前k'+1个字母等于后k'+1个字母(两个浅黄色区域相等),所以next[j+1] = k'+1;
否则,继续k'=next[k']继续循环,直到k'=-1说明已经到达第一个元素,不能继续划分,next[j+1]=0
得到了求next数组的递推方法后,现在用C++实现
void getNext(string str,int next[]){
int len=str.length();
next[0]=-1;
int j=0,k=-1;
while(j<len-1){
if(k==-1||str[j]==str[k])
next[++j]=++k;
else
k=next[k];
}
}
这里解释一下:由于每一轮赋值完next[j]后,k要不然是-1,要不然是next[j](上次匹配的前缀的下一个位置)
如果k=-1,说明next[j+1]=0=k+1;否则如果str[j]==str[k],说明前k+1个字母等于后k+1个字母,直接next[j+1]=k+1
所以循环中if后的语句为"next[++j] = ++k;"
思路
假设str长度为len,重复的子串长度为k,则如果真的由连续多个长度为k的子串重复构成str,那么在对str求next时,由于连续对称性(如图,前后两个虚线框内字符串相等),会从next[k+1]开始,1,2,3...地递增,直到next[len]=len-k,且(len-k)%k==0,表示有整数个k
要一直求到next[len]而不是next[len-1],是因为next[len-1]只是表示前len-1个字母的内部对称性,而没有考虑到最后一个字母即str[len-1]
所以求解很简单:先对str求next数组,一直求到next[len],然后看看next[len]是否非零且整除k(k=len-next[len])
class Solution {
public boolean repeatedSubstringPattern(String s) {
int len=s.length();
int[] next=new int[len+1];
next[0]=-1;
int j=0,k=-1;
while(j<len){
if(k==-1||s.charAt(j)==s.charAt(k)){
next[++j]=++k;
}else{
k=next[k];
}
}
return (next[len]>0)&&next[len]%(len-next[len])==0;
}
}
最新文章
- word20161217
- leetcode174. Dungeon Game
- 用cookie记住用户名
- php之CI框架多语言的用法
- HDU 2222 &; ac自动机模板
- CI如何接受POST请求中的JSON数据
- netstat -aon|findstr 8888 终止进程
- tcpdump抓包规则命令大全
- Python进阶之面向对象编程(二)
- 如何在 静态编译的QT 5.5.1 中 使用数据库插件连接 ODBC(调用静态插件)
- BZOJ 1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛( dp )
- C++指针和引用简介
- wcf契约版本处理与异常处理(随记)
- 团队作业八—第二次团队冲刺(Beta版本) 第 1 天
- PHP时间戳和日期互转换
- 最强AngularJS资源合集
- vue解决加载闪烁问题
- 浅谈_依赖注入 asp.net core
- vue修改端口号
- 更新 是 可用的 针对 安卓 软件开发包和工具 Updates are available for android software development packages and tools
热门文章
- VC中包含的头文件名不区分大小写
- Ubuntu 12.04源
- log4cxx安装使用
- python 之format字符串格式化
- 两个div并列居中显示——当display:inline;时,div的宽高不起作用即两个div重叠显示
- UVA 674 Coin Change 硬币转换(完全背包,常规)
- BZOJ 1806: [Ioi2007]Miners 矿工配餐
- oracle的clob转换varchar2
- epoch,iteration,batch,batch_size
- 天坑之mysql乱码问题以及mysql重启出现1067的错误解决