AcWing 776. 字符串移位包含问题

AcWing 776. 字符串移位包含问题

1. 地址

    https://www.acwing.com/problem/content/778/

2. 题解

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    string s;
    string s1;
    cin >> s;
    cin >> s1;
    if(s.size() < s1.size()){
        swap(s,s1);
    }
    //移位
    for(int i=0;i<s.size();i++){
        //主串进行移位
        //需要注意：string的substr()方法代表取子串，substr(1)代表取从下标1到结尾的子串
        s = s.substr(1) + s[0];
        //遍历起点
        for(int j=0;j + s1.size() <= s.size();j++){
            int k;
            //遍历子串
            for(k=0;k<s1.size();k++){
                if(s[j+k] != s1[k]){
                    break;
                }
            }
            if(k == s1.size()){
                puts("true");
                return 0;
            }
        }
    }
    puts("false");
    return 0;
}
//本题可以进行优化，使用kmp算法