数据结构(字符串)—— 循环旋转字符串的判断

题目

请设计一个线性时间的算法,判断字符串 S 是否是另一个字符串 S’ 的循环旋转。例如, arc和car是彼此的循环旋转。

思路分析

  1. S 和 S’ ​长度不等时,肯定不是循环旋转
  2. 将 S 扩大到两倍,相当于变为 S=S+S(例如arc变为arcarc),如果S’ 是新生成的S的子串,那么S’ 是S的循环旋转,否则,不是循环旋转。
  3. 因为要求线性时间的算法,所以判断是否是字串时,用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";
}
上一篇:Educational Codeforces round 78 A、B


下一篇:《LeetCode之每日一题》:221.找到字符串中所有字母异位词