human
Can you provide a code to minimum rotations required to get the same String and the other steps required given the following:
Minimum rotations required to get the same String | Set | Prints occurrences of txt [ ] in pat [ ].
Create lps [ ] that will hold the longest prefix suffix values for pattern.
Preprocess the pattern ( calculate lps [ ] array ).
Index for txt [ ] , index for pat [ ].
Mismatch after j matches.
Do not match lps [ 0. . lps [ j - 1 ] ] characters , they will match anyway.
Fills lps [ ] for given pattern pat [ 0. . M - 1 ].
Length of the previous longest prefix suffix.
lps [ 0 ] is always 0.
The loop calculates lps [ i ] for i = 1 to M - 1.
( pat [ i ] != pat [ _len ] ).
This is tricky . Consider the example . AAACAAAA and i = 7. The idea is similar to search step ..
Returns count of rotations to get the same string back.
Form a string excluding the first character and concatenating the string at the end.
Convert the string to character array.
Use the KMP search algorithm to find it in O ( N ) time.
Driver code"
Solution in Python:
assistant
#Here is code to minimum rotations required to get the same String and the other steps required.
 def KMPSearch ( pat , txt ) :
	M = len ( pat )
	N = len ( txt )
	lps = [ 0 ] * M
	computeLPSArray ( pat , M , lps )
	i = 0
	j = 0
	while i < N :
		if pat [ j ] == txt [ i ] :
			j += 1
			i += 1
		if j == M :
			return i - j
			j = lps [ j - 1 ]
		elif i < N and pat [ j ] != txt [ i ] :
			if j != 0 :
				j = lps [ j - 1 ]
			else :
				i = i + 1
def computeLPSArray ( pat , M , lps ) :
	_len = 0
	lps [ 0 ] = 0
	i = 1
	while i < M :
		if pat [ i ] == pat [ _len ] :
			_len += 1
			lps [ i ] = _len
			i += 1
		else :
			if _len != 0 :
				_len = lps [ _len - 1 ]
			else :
				lps [ i ] = 0
				i += 1
def countRotations ( s ) :
	s1 = s [ 1 : len ( s ) ] + s
	pat = s [ : ]
	text = s1 [ : ]
	return 1 + KMPSearch ( pat , text )
s1 = " geeks "
print ( countRotations ( s1 ) )