数据结构与算法实验2020夏第二批（中国石油大学） PA12题解报告——循环移位(Cycle)(Schedule)

目录

题目描述题目分析编码实现

一、题目描述

1. 描述

所谓循环移位是指。一个字符串的首字母移到末尾, 其他字符的次序保持不变。比如ABCD经过一次循环移位后变成BCDA。 给定两个字符串，判断它们是不是可以通过若干次循环移位得到彼此。

2. 输入

由m行组成，每行包含两个由大写字母’A’~'Z’组成的字符串，中间由空格隔开。

3. 输出

对于每行输入，输出这两个字符串是否可以通过循环移位得到彼此：YES表示是，NO表示否。

4. 例

//输入 AACD CDAA ABCDEFG EFGABCD ABCD ACBD ABCDEFEG ABCDEE //输出 YES YES NO NO

5. 限制

0 ≤ m ≤ 5000 1 ≤ |S1|, |S2| ≤ 10^5 时间：2 sec 内存：256 MB

二、题目分析

代码实现

读入两个字符串，如果两字符串长度不同，则直接输出No，否则，则把一个字符串接在其自身后面形成一个新串，然后查询另一个字符串是否是新串的子串，如果是则Yes，否则No。

复杂度分析：

时间复杂度：$O(n)$空间复杂度：$O(n)$

三、编码实现

说明： 下述代码全部为【数据结构与算法实验 OJ 平台】提交过的代码。

#include <stdio.h> #include <string.h> #include <stdlib.h> #define set(S, i) ( (S)[i] - 'A' ) bool Check(char* P, char* T, size_t i) { for (size_t m = strlen(P), j = 0; j < m; j++, i++) { if (P[j] != T[i]) return false; } return true; } long long int Prepare(size_t m) { long long int D = 1; for (size_t i = 1; i < m; i++) D = (D*30) % 1000; return D; } void Update(long long int& hashT, char* T, size_t m, size_t k, long long int D) { hashT = (hashT - set(T, k - 1)*D) % 1000; hashT = (hashT*30 + set(T, k + m - 1)) % 1000; if (hashT < 0) hashT += 1000; } bool Matching(char* P, char* T) { size_t m = strlen(P), n = strlen(T); long long int D, hashP = 0, hashT = 0; D = Prepare(m); for (size_t i = 0; i < m; i++) { hashP = (hashP*30 + set(P, i)) % 1000; hashT = (hashT*30 + set(T, i)) % 1000; } for (size_t k = 0;;) { if (hashT == hashP && Check(P, T, k)) return true; if (++k>n - m) return false; else Update(hashT, T, m, k, D); } } int main() { char* p1 = (char*)malloc(sizeof(char)*(100010)); char* p2 = (char*)malloc(sizeof(char)*(100010 * 2)); do { if (scanf("%s %s", p1, p2) == EOF) break; int n1, n2; n1 = strlen(p1); n2 = strlen(p2); if (n1 != n2) printf("NO\n"); else { int i; for (i = n2; i < n2 * 2 - 1; i++) p2[i] = p2[i - n2]; p2[i] = '\0'; if (Matching(p1, p2)) printf("YES\n"); else printf("NO\n"); } } while (1); return 0; }