字符串循环移位包含问题

时间:2023-01-03 21:25:52
#include <iostream>
#include <string>
#include <stdio.h>
#include <time.h>

using namespace std;

void PrintCharArray(string a);
bool CharContain(string src, string des);

int main(int argc, char *argv[])
{
/*
* 字符串的移位包含问题:给定两个字符串s1和s2,要求判断s2是否能够被s1做循环移位(rotate)得到的字符串包含。
* eg: s1 = AABCD, s2 = CDAA, 返回true; s1 = ABCD, s2 = ACBD, 返回false.
* 注意s1循环移位所有可能包含于s1s1中,因此,可以用string的find方法判断s1s1中是否包含s2.
*/

//string src = "AABBCD";
//string des = "CDAA";
//PrintCharArray(src);
//PrintCharArray(des);
//CharContain(src, des);

clock_t start_time = clock();

CharContain("AABBCD", "CDAA");
CharContain("ABCD", "ACBD");

clock_t end_time = clock();

cout << "Running time of CharContain1 is "
<< static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC * 1000
<< "ms." << endl;

return 0;
}

void PrintCharArray(string a)
{
if (!a.empty())
{
int len = a.size();
for (int i = 0; i < len; i++)
{
cout << a[i];
}
}
cout << endl;
}

bool CharContain(string src, string des)
{
int len = src.size();
string tmp = src + src;

int index = tmp.find(des);

if (index != -1)
{
cout << "Case One: " << endl;
for (int i = index; i < len * 2; i++)
{
cout << tmp[i];
}
cout << endl;
cout << "s2 in s1s1." << endl << endl;
return true;
}
else
{
cout << "Case Two: " << endl;
cout << "s2 not in s1s1." << endl;
return false;
}
}


字符串循环移位包含问题