Title Description

Given a non empty string s , Check whether it can be formed by repeating one of its substrings multiple times .
Example 1

 Input : s = "abab"
 Output : true
 explain :  But by substring  "ab"  Repeat twice to form .

Example 2

 Input : s = "aba"
 Output : false

Example 3

 Input : s = "abcabcabcabc"
 Output : true
 explain :  But by substring  "abc"  Repeat for four times . ( Or substring  "abcabc"  Repeat twice to form .)

Simple question I hit hard , At the beginning of this problem, we are going to use violence to do , But it feels like a simple question , I think there must be a clever way to solve the problem . After thinking about it later, I found that the effect is almost the same as that of violence , Only slightly better in solving problems . See the official replacement document later , There is KMP, As soon as I see this, I feel like a waste . Due to KMP A state that has been almost forgotten , I'll explain it after the rookie relearns , Let's talk about it first “ violence ” and “ displacement ” Two ways to solve problems .

Their thinking

1. violence
If a length is N String S Meet the conditions , that S It must have a length of n Substring of s’ Splice several times ( Greater than 1 Time ) constitute . The following conditions must be met ：

	S=s's's'... N yes n Integer multiple  s'[i] = S[i+kn]     (0< = i< n  , 0 <= k < N/n )

We can use violence , The length will be n Substring of s’ To find out , Then iterate through the string S. Judge the above conditions .

    bool repeatedSubstringPattern(string s) {
    
	int n = s.size();
	for(int i = 1; i <= n/2; ++i) {
     // stay S Half the length of... Was not found , Indicates that the string does not match .
		if(n % i == 0) {
    	// If the string S The length of is not an integer multiple of the length of the current substring   Just skip 
			int flag=1; // As a marker whether to find , Find early return 
			for(int j = i; j < n; ++j)//i Represents the length of the current search substring 
				if (s[j] != s[j - i]) {
    
				flag=0;
				break;
			}
			if(flag)
				return 1;
		}
	}
	return 0;
    }

2. displacement
We already know S=s’s’s’…, So we're going to S The first substring in s’ Move to S Last go , The new string formed should be the same as S They are equal. . We can get the substring through multiple shifts . The general process is as follows ：

 for example ：S=abcabc
 Shift once ：cabcab
 Shift twice ：bcabca
 Shift three times ：abcabc

Shift for the third time to get the string and S matching , You can get S Meet the conditions , Substring s’=“abc”.

    bool repeatedSubstringPattern(string s) {
    
	int n=s.size();
	string temp;
	for(int i=1;i<=n/2;i++){
      stay S Half the length of... Was not found , Indicates that the string does not match .
		temp=s.substr(i,n-i)+s.substr(0,i);// utilize subtr(start,length) Function to realize the operation of shift 
		if(temp==s)
			return 1;
	}
	return 0;
    }

This kind of thinking is one of the correct ways to solve problems , Don't doubt this idea . But the quality of the code I wrote is not high , Although it can pass , But it consumes a lot of memory and running time . After watching the improvement of the big guys , Using the idea of sliding windows +find Built in functions , One line of code is done directly , There is a long way to go .

bool repeatedSubstringPattern(string s) {
    
      return (s + s).find(s, 1) != s.size();//(s + s).find(s, 1) return s.size（） Indicates that the string is not satisfied with 
  }

str1.find(str2,pos) # from str1 Of the pos From one position , In string str1 Looking for strings in str2, The return is str1 stay str2 The first place in .

Readers can run the following code to deepen their understanding .

	string s="abcd";
	string ss=s+s; //ss="abcdabcd"
	cout<<ss.find(s,0);// take 0 become 1,2,3,4,5 Have a try 

3.KMP Algorithm
I owe you first , When you are proficient in learning, make up .KMP Algorithm