算法-KMP-重复的子字符串

淩亂°似流年 2022-11-30 12:33 136阅读 0赞

# 算法-KMP-重复的子字符串 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/repeated-substring-pattern/solution/java-yi-xing-dai-ma-jie-jue-zhong-fu-zi-chuan-wen-/

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70_pic_center]

# 2 暴力枚举法 #

## 2.1 思路 ##

从长度为1的窗口开始翻滚，每次用substring方法比较，如果不同，就停止，并将窗口大小加一再次比较。

## 2.2 代码 ##

class Solution { 
        public boolean repeatedSubstringPattern(String s) { 
            if(s == null){ 
                return false;
            }
    
            for(int i = 1; i <= s.length() / 2; i++){ 
                String base = s.substring(0, i);
                int j = i;
                // j <= s.length() - i是防止数组越界
                for(; j <= s.length() - i; j += i){ 
                    if(!s.substring(j, j + i).equals(base)){ 
                        break;
                    }
                }
                if(j >= s.length()){ 
                    return true;
                }
            }
            return false;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200824114451239.png_pic_center]

# 3 枚举法-优化 #

## 3.1 思路 ##

从长度为1的窗口开始翻滚，每次用substring方法比较，如果不同，就停止，并将窗口大小加一再次比较。

但有个优化，即每次取窗口长度时，先判断是否能被字符串长度整除，如果不行直接跳过该大小的窗口。

## 3.2 代码 ##

class Solution { 
        public boolean repeatedSubstringPattern(String s) { 
            if(s == null){ 
                return false;
            }
    
            for(int i = 1; i <= s.length() / 2; i++){ 
                if(s.length() % i != 0){ 
                    continue;
                }
                String base = s.substring(0, i);
                int j = i;
                for(; j < s.length() ; j += i){ 
                    if(!s.substring(j, j + i).equals(base)){ 
                        break;
                    }
                }
                if(j >= s.length()){ 
                    return true;
                }
            }
            return false;
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200824114938972.png_pic_center]  
O(N^2)

*  N为字符串总长，枚举窗口长度时间复杂度O(N)；每次窗口翻滚时间复杂度O(N)，所以是O(N^2)

## 3.4 空间复杂度 ##

O(1)

# 4 字符串匹配 #

## 4.1 思路 ##

[重复的子字符串-官方题解][-]方法3可证明，要求重复的子字符串，只要将该字符串重复一次append在该字符串后面，并去掉首位字符串，得到的字符串只要contains原始字符串，那就说明可由重复的子字符串构成。

也可以参考[简单明了！！关于java两行代码实现的思路来源][java]

## 4.2 代码 ##

if(s == null){ 
                return false;
            }
            return (s + s).substring(1, s.length()*2-1).contains(s);

## 4.3 时间复杂度 ##

![在这里插入图片描述][20200824120111933.png_pic_center]

## 4.4 空间复杂度 ##

O(1)

# 参考文档 #

*  [重复的子字符串-官方题解][-]
 *  [程序员小灰-漫画：什么是KMP算法？][-_KMP]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/f14ba68bf5a34b8ebb7ab6912fc8fbf3.png
[20200824114451239.png_pic_center]: /images/20221123/7c7472199fee47bb9178d5188ae68fff.png
[20200824114938972.png_pic_center]: /images/20221123/5767ad7f487f4d569b90f879ba3407b2.png
[-]: https://leetcode-cn.com/problems/repeated-substring-pattern/solution/zhong-fu-de-zi-zi-fu-chuan-by-leetcode-solution/
[java]: https://leetcode-cn.com/problems/repeated-substring-pattern/solution/jian-dan-ming-liao-guan-yu-javaliang-xing-dai-ma-s/
[20200824120111933.png_pic_center]: /images/20221123/523641fda4ad4bcb97b3981eb8a9321e.png
[-_KMP]: https://blog.csdn.net/bjweimengshu/article/details/104528964/