2021-02-12：如何判断两个字符串是否互为旋转字符串？
福哥答案2021-02-12：
假设字符串str1是“ABCDE”，字符串str2是“CDEAB”。字符串str2可以拆分成“CDE”和“AB”，可以拼成“ABCDE”。所以str1和str2互为旋转字符串。
解法：
1.判断str1和str2的字符串长度是否相等。不等返回false；相等进行下一步。
2.设str=str1+str1，判断str是否包含str2。如果包含，是旋转字符串。如果不包含，说明不是旋转字符串。
字符串是否包含子字符串，可以用相应语言的系统自带函数，也可以用kmp算法。
代码用golang编写，代码如下：
package main
import (
"fmt"
"strings"
)
func main() {
str1 := "ABCDE"
str2 := "CDEAB"
ret := rotateString1(str1, str2)
fmt.Println("1.系统自带函数：", ret)
ret = rotateString2(str1, str2)
fmt.Println("2.kmp算法：", ret)
}
//1.系统自带函数
func rotateString1(A string, B string) bool {
return len(A) == len(B) && strings.Contains(A+A, B)
}
//2.kmp算法
func rotateString2(A string, B string) bool {
return len(A) == len(B) && kmp(A+A, B) >= 0
}
func kmp(s string, m string) int {
sLen := len(s)
mLen := len(m)
if sLen < mLen {
return -1
}
if mLen == 0 {
return 0
}
next := getNextArray(m)
x := 0
y := 0
for x < sLen && y < mLen {
if s[x] == m[y] {
x++
y++
} else if y > 0 {
y = next[y]
} else {
x++
}
}
if y == mLen {
return x - y
} else {
return -1
}
}
func getNextArray(m string) []int {
mLen := len(m)
if mLen == 1 {
return []int{-1}
}
next := make([]int, mLen)
next[0] = -1
cn := 0
for i := 2; i < mLen; i++ {
if m[i-1] == m[cn] {
cn++
next[i] = cn
i++
} else if cn > 0 {
cn = next[cn]
} else {
i++
}
}
return next
}
执行结果如下：
在这里插入图片描述
