【Leetcode字符串】459. 重复的子字符串（民间巧妙移位解法和KMP！！）

• Leetcode459
• • 1.问题描述
  • 2.解决方案
  • • 解法一：民间巧妙移位解法
    • 解法二：暴力
    • 解法三：KMP

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string str=s+s;
        string str1=str.substr(1,str.size()-2);
        if(str1.find(s)==string::npos) return false;
        else return true;
    }
};

	//暴力代码
	public  boolean repeatedSubstringPattern(String s) {
        for(int i = 1; i < s.length(); i++) {
            String str = rotate(s.toCharArray(),i);
            if(s.equals(str)) return true;
        }
        return false;
    }


    public  String rotate(char[] nums, int k) {
        k = k % nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
        return String.valueOf(nums);
    }

    public  void reverse(char[] nums, int begin, int end) {
        int i = begin, j = end;
        while(i < j) {
            char temp = nums[i];
            nums[i++] = nums[j];
            nums[j--] = temp;
        }
    }

KMP