基于字符串移位包含的问题详解

代码如下所示：

复制代码 代码如下:

/************************************************************************/
/* 给定两个字符串s1和s2，要求判定s2是否能被s1做循环移位得到的字符串所包含
例如，给定s1 = AABCD, s2 = CDAA,返回true，给定s1 = ABCD， s2 = ACBD，返回false*/
/************************************************************************/
#include "stdafx.h"
#include <iostream>
using namespace std;
//穷举法
int IfRotateContain1(char *str1, const char *str2);
//空间换取时间法
int IfRotateContain2(char *str1, const char *str2);
int _tmain(int argc, _TCHAR* argv[])
{
    char str1[] = "AABBCD";
    char str2[] = "CDAA";
    int ret1 = IfRotateContain1(str1, str2);
    int ret2 = IfRotateContain2(str1, str2);
    cout << ret1 << endl;
    cout << ret2 << endl;
    return 0;
}
int IfRotateContain1( char *str1, const char *str2 )
{
    int len = strlen(str1);
    for (int i = 0; i < len; i++)
    {
        char temchar = str1[0];
        for (int j = 0;j < len-1; j++)
        {
            str1[j] = str1[j+1];
        }
        str1[len-1] = temchar;
        if (strstr(str1, str2) )
        {
            return 1;
        }
    }
    return 0;
}
int IfRotateContain2( char *str1, const char *str2 )
{
    int len = strlen(str1);
    char *p = new char[len*2+1];
    for (int i = 0; i < len; i++)
    {
        p[i] = str1[i];
        p[i+len] = str1[i];
    }
    for (int j = 0; j < len*2; j++)
    {
        if (strstr(str1, str2))
        {
            return 1;
        }
    }
    delete [] p;
    return 0;
}