编程之美：3.1 字符串移位包含的问题

给一个S1=”AABCD”，判断S2是否能通过S1移位得到，例如S2=“CDAA”，应该返回true。

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

/*
该函数主要是遍历的方法，将所有情况都测试一遍，效率较低
时间复杂度为O(n2)
*/
void function1(string src, string des)
{
    int len = src.length();
    //src += "123";
    //cout << src << endl;
    for (int i = 0; i < len; i++)
    {
        char temp = src[0];
        for (int j = 0; j < len - 1; j++){
            src[j] = src[j + 1];
        }
        src[len -1] = temp;

        //判断是否包含该字符串
        if (src.find(des) != string::npos){
            cout << "true" << endl;
            return;
        }
    }
}
/*
This function is based on the theory that if s2 can roll from
s1, then s2 must be a substr of s1s1.
*/
void function2(string src, string des)
{
    src += src;
    cout << src << endl;

    if (src.find(des) != string::npos){

        cout << "true" << endl;
        return;
    }

    return;
}
int main()
{
    string src;
    string des;

    while (cin >> src){
        cin >> des;

        //在function1中对src 和 des的改变将不会影响主程序的src和des,这和java有一定的区别
        //function1(src, des);
        //cout << src << endl;
        function2(src, des);
    }

}

扩展问题： 如果不能申请过多新的空间，怎么解决这个问题。（待完善）

阅读更多