题目描述:

给出字符串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;
}
分类: KmpString

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status