776.字符串移位包含问题

对于一个字符串来说，定义一次循环移位操作为：将字符串的第一个字符移动到末尾形成新的字符串。
给定两个字符串s1和s2，要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。
例如CDAA是由AABCD两次移位后产生的新串BCDAA的子串，而ABCD与ACBD则不能通过多次移位来得到其中一个字符串是新串的子串。

输入格式

共一行，包含两个字符串，中间由单个空格隔开。
字符串只包含字母和数字，长度不超过$30$。

输出格式

如果一个字符串是另一字符串通过若干次循环移位产生的新串的子串，则输出true，否则输出false。

输入样例：

AABCD CDAA

输出样例：

true

AC代码

普通的每一项都判断。

思路为：
基于他是可以有首尾相连的字串的形式，于是我们将字符串复制一份到原字符串后面。
每一项的判断，优先认为其符合，判断中遇到不符合就跳出。否则就是符合，只要有意向符合就可以跳出所有循环。
这里考虑到的是循环中要判断出什么（特判中赋值），否则就是什么（这个是一开始的初值）。

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string a, b;
    cin >> a >> b;

    // 保证a为匹配串，b为待匹配串
    if(a.size() < b.size()) swap(a, b);

    int flag = 0;
    int len = a.size();
    a += a;  // 将字符串加到自身后
    for(int i = 0; i<len; i++){
        int same = 1;  // 先默认是相等的
        for(int j = 0;j<b.size();j++){
            if(a[i+j] != b[j]){
                same = 0;
                break;
            }
        }
        if(same){
            flag = 1;
            break;
        }
    }

    cout << (flag ? "true" : "false") << endl;

    return 0;
}

优化1

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string a, b;
    cin >> a >> b;

    if(a.size() < b.size()) swap(a, b);

    int flag = 0;
    int len = a.size();
    a += a;
    for(int i = 0; i<len; i++){
        int same = 1;  // 先默认是相等的
        for(int j = 0;j<b.size();j++){
            if(a[i+j] != b[j]){
                same = 0;
                break;
            }
        }
        // 其实到这里的循环已经没有必要了
        if(same){
            cout << "true" << endl;
            return 0;
        }
    }
    // 否则才会运行到这里
    cout << "false" << endl;
    return 0;
}

优化2（很巧的思维）

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string a, b;
    cin >> a >> b;

    if(a.size() < b.size()) swap(a, b);

    int flag = 0;
    int len = a.size();
    a += a;
    for(int i = 0; i<len; i++){
        int k = 0;
        for(int j = 0;j<b.size();j++)
        if(a[i+j] == b[j]) k ++;
        // 很巧的方法，如果上面的判断都正确，那么相等
        if(k == b.size()){
            cout << "true" << endl;
            return 0;
        }
    }
    // 否则才会运行到这里
    cout << "false" << endl;
    return 0;
}

AC代码

沿用上一份代码的思路，但是用substr提取一部分字符串来判断

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string a, b;
    cin >> a >> b;

    if(a.size() < b.size()) swap(a, b);

    int len = a.size();
    a += a;
    for(int i = 0; i<len; i++){
        if(b == a.substr(i, b.size())){
            puts("true");
            return 0;
        }
    }
    // 否则才会运行到这里
    cout << "false" << endl;
    return 0;
}