C++程序检查字符串是否可以通过旋转另一个字符串2个位置获得

介绍

有时候我们需要检查一个字符串是否可以通过将它旋转2个位置而变成另一个字符串。例如，对于字符串“abcde”，我们可以通过将它旋转2个位置变成“cdeab”或者“deabc”等等。这种情况下，我们称“cdeab”是“abcde”的旋转字符串。在这篇文章中，我将会介绍如何用C++程序检查一个字符串是否可以通过旋转另一个字符串2个位置获得。

解法

为了解决这个问题，我们可以采用类似于字符串匹配中KMP算法的思路。具体来说，我们可以先将两个字符串连起来，然后在这个新的字符串中利用KMP算法查找是否存在长度为n的前缀等于另一个字符串的长度为n的后缀，其中n为字符串长度，如果存在这样的位置，那么说明原字符串是可以通过旋转2个位置变成另一个字符串的。

下面是C++代码实现：

#include <iostream>
#include <string>

using namespace std;

//KMP算法框架，用于查找模式字符串在文本字符串中的出现位置
//返回模式字符串在文本字符串中首次出现的位置（从0开始），如果不存在则返回-1
int KMP(string text, string pattern) {

    //计算最长公共前后缀的部分匹配表lps（longest prefix which is also suffix）
    int lps[pattern.length()];

    //初始化lps数组的第一个值
    lps[0] = 0;

    //从i=1开始计算lps[i]
    int i = 1;

    //表示当前已经匹配成功的前缀的长度
    int len = 0;

    while (i < pattern.length()) {

        //如果新加入一个字符与前面匹配的最长前后缀的下一个字符匹配成功，
        //那么当前的最长前后缀的长度加1
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        }

        //如果新加入的字符不能与前面的最长前后缀匹配成功，
        //那么需要依据lps数组回溯到前面的匹配位置继续匹配
        else {

            if (len != 0) {
                len = lps[len - 1];
            }

            else {
                //如果当前没有匹配成功的前缀，那么可以直接匹配下一个字符
                lps[i] = 0;
                i++;
            }

        }

    }

    //在文本字符串中查找模式字符串
    int j = 0; //j用于标记文本字符串的位置

    for (int i = 0; i < text.length(); i++) {

        //如果文本字符串的当前字符与模式字符串的当前字符匹配成功，
        //那么继续匹配下一个字符
        if (text[i] == pattern[j]) {
            j++;
        }

        //否则需要根据当前匹配的部分回溯到新的位置继续匹配
        else {
            //j不能直接减小，因为可能存在当前字符与上一个匹配字符匹配成功的情况
            //所以要利用lps数组回溯到上一个合法的匹配位置
            if (j != 0) {
                j = lps[j - 1];
                i--; //否则文本字符串的下一个字符就会被跳过
            }
        }

        //如果模式字符串的所有字符都已经被匹配成功，
        //那么说明模式字符串在文本字符串中出现了
        if (j == pattern.length()) {
            return i - pattern.length() + 1; //返回模式字符串在文本字符串中//的起始位置
        }

    }

    //如果没有找到，返回-1
    return -1;

}


//检查一个字符串是否可以通过旋转另一个字符串2个位置获得
bool checkRotation(string str1, string str2) {

    //如果两个字符串长度不一样，那么肯定不行
    if (str1.length() != str2.length()) {
        return false;
    }

    //将两个字符串连接起来
    string text = str1 + str1;

    //检查两个字符串是否相等，如果相等那么也算是一种旋转（旋转了0个位置）
    if (str1 == str2) {
        return true;
    }

    //检查是否存在长度为n的前缀等于另一个字符串的长度为n的后缀，
    //其中n为字符串长度
    else {
        string pattern = str2.substr(2) + str2.substr(0, 2);
        int pos = KMP(text, pattern);
        return pos != -1;
    }

}

int main() {

    string str1 = "abcde";
    string str2 = "cdeab";

    if (checkRotation(str1, str2)) {
        cout << str2 << " is a rotation of " << str1 << endl;
    }

    else {
        cout << str2 << " is not a rotation of " << str1 << endl;
    }

    return 0;

}

结论

在本篇文章中，我们介绍了如何用C++程序检查一个字符串是否可以通过旋转另一个字符串2个位置获得。具体来说，我们采用了类似于字符串匹配中KMP算法的思路，先将两个字符串连接起来，然后在这个新的字符串中利用KMP算法查找是否存在长度为n的前缀等于另一个字符串的长度为n的后缀，其中n为字符串长度，如果存在这样的位置，那么说明原字符串是可以通过旋转2个位置变成另一个字符串的。