Loading... [来自KeChang](https://blog.silvery.me/) **题目描述:** 给出字符串A和B,判断A是否是B的进行循环移位得到的子串。 例如,A="ABC",B="BCDEFA",则是。 **输入格式:** 输入包含多组测试数据。 每组数据占一行,包含两个空格隔开的字符串A和B。 **输出格式:** 每组数据输出一行结果,如果A是循环移位子串输出"yes",否则输出"no"。 **数据范围:** 输入最多包含100组数据。 字符串长度不超过100且只包含大写字母。 **输入样例:** ``` ABC BCDEFA ABC BADEFC ``` **输出样例:** ``` yes no ``` **题目分析:** ·`s` \* 2 便于判断循环处。 · KMP **代码实现:** ``` #include <iostream> #include <vector> #include <string> using namespace std; string a, b; bool kmp() { if ((int)a.length() > (int)b.length()) return false; string A = " " + a; string B = " " + b + b; int n = A.length(), m = B.length(); vector <int> ne(220); for (int i = 2, j = 0; i < n; ++i) { while (j && A[i] != A[j + 1]) j = ne[j]; if (A[i] == A[j + 1]) ++j; ne[i] = j; } for (int i = 1, j = 0; i < m; ++i) { while (j && B[i] != A[j + 1]) j = ne[j]; if (B[i] == A[j + 1]) ++j; if (j == n - 1) return true; } return false; } int main () { ios::sync_with_stdio(0); cin.tie(0); while (cin >> a >> b) { kmp() ? cout << "yes\n" : cout << "no\n"; } return 0; } ``` 最后修改:2023 年 08 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏