题目
请设计一个线性时间的算法,判断字符串 S 是否是另一个字符串 S’ 的循环旋转。例如, arc和car是彼此的循环旋转。
思路分析
- S 和 S’ 长度不等时,肯定不是循环旋转
- 将 S 扩大到两倍,相当于变为 S=S+S(例如arc变为arcarc),如果S’ 是新生成的S的子串,那么S’ 是S的循环旋转,否则,不是循环旋转。
- 因为要求线性时间的算法,所以判断是否是字串时,用KMP匹配算法
C++代码
#include<iostream>
#include <algorithm>
#include <string>
using namespace std;
//计算字符串特征向量(优化版)
int* findNext(string P) {
int i, k;
int m = P.length(); // m为模式P的长度
int* next = new int[m]; // 动态存储区开辟整数数组
next[0] = -1;
i = 0; k = -1;
while (i < m - 1) { // 若写成 i < m 会越界
while (k >= 0 && P[k] != P[i]) // 采用 KMP 找最大首尾子串
k = next[k]; // k 递归地向前找
i++;
k++;
if (P[k] == P[i])
next[i] = next[k]; // 前面找 k 值,没有受优化的影响
else
next[i] = k; // 取消if判断,则不优化
}
return next;
}
//KMP匹配
int KMPStrMatching(string T, string P, int* N) {
int i = 0;
int j = 0;
int tLen = T.length(); // 目标的长度
int pLen = P.length(); // 模式的长度
if (tLen < pLen) // 若目标比模式短,匹配无法成功
return -1;
while (i < tLen && j < pLen) { // 反复比较,进行匹配
if (j == -1 || T[i] == P[j])
i++, j++;
else j = N[j]; // 不相等,按照特征向量调整
}
if (j >= pLen)
return (i - pLen); // 注意仔细算下标
else
return -1;
}
int main() {
string s1, s2;
cin >> s1 >> s2;
if (s1.length() != s2.length()) {
cout << "No";
return 0;
}
s1 = s1 + s1;
int* next = new int[100];
next = findNext(s2);
if (KMPStrMatching(s1, s2, next) == -1)
cout << "No";
else
cout << "Yes";
}