题目描述
对于一个字符串来说,定义一次循环移位操作为:将字符串的第一个字符移动到末尾形成新的字符串。
给定两个字符串 s1和 s2,要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。
例如 CDAA 是由 AABCD 两次移位后产生的新串 BCDAA 的子串,而 ABCD 与 ACBD 则不能通过多次移位来得到其中一个字符串是新串的子串。
输入格式
共一行,包含两个字符串,中间由单个空格隔开。
字符串只包含字母和数字,长度不超过 30
。
输出格式
如果一个字符串是另一字符串通过若干次循环移位产生的新串的子串,则输出 true,否则输出 false。
样例
输入样例:
AABCD CDAA
输出样例:
true
双指针写法 c++代码;时间复杂度:O(n),n为较长的那个字符串的长度;
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
string s,t;
cin >> s >> t;
if(s.size() < t.size()) swap(s,t);
s += s; //因为要循环移位进行判断,不妨直接把长的那个字符串变长一倍;
int i = 0,j = 0;
while(i < s.size() && j < t.size()){
//双指针算法,当两个指针所指字符都相等时,同时向后移动一位,若不相等,j指针回到原点,再继续判断;
if(s[i] != t[j]){
i++;
j = 0;
}else{
i++;
j++;
}
}
//跳出循环时如果j指针指向t字符串的末尾之后,说明t字符串是字串,返回true;
if(j == t.size()) printf("true");
else printf("false"); //如果i指针越界,说明t字符串不是s字符串的字串;
return 0;
}