842      阿裏雲  技術社區[雲棲]

編程之美之字符串移位包含問題

【題目】

給定兩個字符串s1和s2，要求判斷s2是否能夠被通過s1做循環移位（rotate）得到的字符串包含。例如，S1=AABCD和s2=CDAA，返回true；給定s1=ABCD和s2=ACBD，返回false。

【分析】

【思路一】

從題目中可以看出，我們可以使用最直接的方法對S1進行循環移動，再進行字符串包含的判斷，從而遍曆其所有的可能性。

字符串循環移動，時間複雜度為O（n），字符串包含判斷，采用普通的方法，時間複雜度為O（n*m），總體複雜度為O（n*n*m）。

字符串包含判斷，若采用KMP算法，時間複雜度為O（n），這樣總體的複雜度為O（n*n）。若字符串的長度n較大，顯然效率比較低。其中n為S1的長度，m為S2的長度。

【思路二】

我們也可以對循環移位之後的結果進行分析。
以S1 = ABCD為例，先分析對S1進行循環移位之後的結果，如下所示：
ABCD--->BCDA---->CDAB---->DABC---->ABCD……
假設我們把前麵的移走的數據進行保留，會發現有如下的規律：
ABCD--->ABCDA---->ABCDAB---->ABCDABC---->ABCDABCD……
因此，可以看出對S1做循環移位所得到的字符串都將是字符串S1S1的子字符串。如果S2可以由S1循環移位得到，那麼S2一定在S1S1上，這樣時間複雜度就降低了。

【代碼一】

/*********************************
*   日期：2014-5-15
*   作者：SJF0115
*   題號: 字符串移位包含問題
*   來源：編程之美
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

bool IsRotate(char* str1,char* str2){
    int i,j;
    if(str1 == NULL || str2 == NULL){
        return false;
    }
    int len = strlen(str1);
    //循環移位
    for(i = 0;i < len;i++){
        char temp = str1[0];
        //移動一位
        for(j = 1;j < len;j++){
            str1[j-1] = str1[j];
        }
        str1[len-1] = temp;
        //判斷str1中是否包含str2
        if(strstr(str1,str2) != 0){
            return true;
        }
    }
    return false;
}

int main(){
    char str1[6] = "AABCD";
    char str2[5] = "CDAA";
    bool result = IsRotate(str1,str2);
    cout<<result<<endl;
    return 0;
}

【代碼二】

/*********************************
*   日期：2014-5-15
*   作者：SJF0115
*   題號: 字符串移位包含問題
*   來源：編程之美
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

bool IsRotate(char* str1,char* str2){
    int i,j;
    if(str1 == NULL || str2 == NULL){
        return false;
    }
    int len1 = strlen(str1);
    char* str3 = new char(len1*2+1);
    strcpy(str3,str1);
    strcat(str3,str1);
    //str3 = str1+str1
    if(strstr(str3,str2) != 0){
        return true;
    }
    return false;
}

int main(){
    char str1[6] = "AABCD";
    char str2[5] = "CDAA";
    bool result = IsRotate(str1,str2);
    cout<<result<<endl;
    return 0;
}

最後更新：2017-04-03 12:56:39

  上一篇： [Cocos2d-x v3.x]序列幀動畫

  下一篇： ubuntu 14.04中安裝Jenkins