C++ 检查任意字符串的左右移是否得到给定字符串

一个字符集合由字符串数据类型表示。它逻辑上使用字母、数字、符号和空格排列。大多数计算机语言用单引号或双引号将字符串括起来以区分它们与其他数据类型。

程序员经常使用字符串来执行一些输入和输出操作，存储和操作文本数据等。字符串可以进行连接（合并两个或多个字符串）、子字符串提取（获取字符串的一部分）和搜索字符串中的特定字符或模式等一些常见操作。

方法

我们可以使用以下方法来确定字符串的左右移是否得到每一个字符串 −

方法1. 蛮力方法 −

方法2. 检查子字符串 −

方法1：蛮力方法

使用蛮力方法，生成输入字符串的所有左右移，并将每一个与目标字符串进行比较。这种方法的时间复杂度，其中n是字符串的长度，为O(n2)。

语法

通过迭代原始字符串的所有潜在左右移，并将它们与给定字符串进行比较，可以确定任意字符串的左右移是否得到给定字符串。这种策略的一般语法如下所示 −

string_shift_check (original_string, given_string):
   n = length of original string
   for int i from 0 to n-1:
      left shift = original string[i:n] + original string[0:i]
      right shift = original string[n-i:n] + original string[0:n-i]
      if left shift == given string or right shift == given string:
         return True
   return False

步骤

确定一个字符串的左移和右移是否导致提供的字符串的暴力方法涉及测试字符串的每个可能的移位，并确定它们中是否有一个与给定的字符串匹配的。算法如下所示−

步骤 1 − 首先将一个变量初始化为0，表示当前的移位计数。

步骤 2 − 当移位次数小于字符串长度时−

• 通过将第一个字符移动到字符串末尾来左移字符串。

• 验证移位后的字符串与提供的字符串是否匹配。如果匹配，则返回 true。

• 通过将最后一个字符移动到字符串开头来右移字符串。

• 验证移位后的字符串与提供的字符串是否匹配。如果匹配，则返回 true。

• 将移位计数加1。

步骤 3 − 在尝试了所有可能的移位后，如果没有发现匹配，则返回 false。

示例1

此实现说明 Shifted String 函数接收两个字符串参数 s 和 target，并返回一个布尔值，指示 target 是否是 s 的左移或右移。

在确定 target 是否是 s 的移位版本之前，函数首先确认两个字符串的长度是否相等。然后，它通过结合每个可能的移位位置之前和之后的子字符串来构建新字符串。如果左移或右移后的字符串与目标字符串相似，则返回 true。如果不是，则返回 false。

在主函数中，我们定义了两个示例字符串 s 和 target，并使用这些字符串调用 Shifted String 方法。程序然后指示 target 是否是 s 的移位形式。

#include <iostream>
#include <string>

using namespace std;

bool isShiftedString(string s, string target) {
   if(s.length() != target.length()) {
      return false;
   }
   int n = s.length();
   for(int i = 0; i < n; i++) {
      string leftShift = s.substr(i) + s.substr(0, i); // left shift the string
      string rightShift = s.substr(n-i) + s.substr(0, n-i); // right shift the string
      if(leftShift == target || rightShift == target) {
         return true;
      }
   }
   return false;
}

int main() {
   string s = "abcde";
   string target = "cdeab";
   if(isShiftedString(s, target)) {
      cout << "The string is shifted." << endl;
   } else {
      cout << "The string is not shifted." << endl;
   }
   return 0;
}

输出

The string is shifted.

方法2：检查子字符串

通过”检查子字符串”方法可以确定一个较小的字符串是否是一个较长字符串的一部分。这个过程涉及将与较小字符串相同长度的各个子字符串与较小字符串本身进行比较，同时遍历较长字符串。如果两个字符串匹配，这就确认了较短的字符串确实是较大文本的一个子集。为了增加这篇文章中的复杂性和句子长度的变化，这个思路应该被分解成简单而有吸引力的部分。

语法

下面的语法可以用来确定任何字符串的左移和右移是否会得到给定字符串 −

if (string_to_check_in.find(substring_to_check) != -1):
   //Substring found in string, so it is a left or right shift
else:
   //Substring not found, so it is not a left or right shift

步骤

以下算法用于确定字符串的左移和右移是否产生给定字符串：

步骤1 - 输入和目标字符串。

步骤2 - 验证输入字符串的长度和目标字符串的长度是否相等。如果不相等，返回False。

步骤3 - 要构建一个新的序列，必须将输入字符串与输出字符串合并。

步骤4 - 要确认输入字符串是否包含在新构建的序列中，需要进行比较。

步骤5 - 如果两个字符串完全一致，则答案为True；否则答案为False。

示例2

下面是一个C++代码，用于判断左移和右移任何字符串是否会产生给定的字符串：

这个示例研究两个数组s1和s2之间的关系，以观察它们是否共享任何相似的字符串。通过保持s1和s2的长度相同的前提，它们被合并成一个名为”s1s1″的数组。进一步对该数组进行检查，以确定是否可以找到s2的一部分，搜索的结果将输出”true”或”false”。这种基本的关联反应技术被用来进一步评估s1和s2的左右字段，以确认这两个序列之间的关联。

#include <iostream>
#include <string>

using namespace std;

bool checkForSubstring(string s1, string s2) {
   if (s1.length() != s2.length()) {
      return false;
   }

   string s1s1 = s1 + s1;

   if (s1s1.find(s2) != string::npos) {
      return true;
   }

   return false;
}
int main() {
   string s1 = "abcd";
   string s2 = "cdab";

   if (checkForSubstring(s1, s2)) {
      cout << "Yes, left or right shift of string " << s1 << " results in " << s2 << endl;
   } else {
      cout << "No, left or right shift of string " << s1 << " does not result in " << s2 << endl;
   }
   return 0;
}

输出

Yes, left or right shift of string abcd results in cdab

结论

对于这个主题，我们给定了一个字符串，并且我们需要确定这个字符串是否可以通过反复应用左移和右移来生成。

简单地将提供的字符串与本身进行连接，并确定新字符串是否保留原始字符串，就可以解决这个问题。如果是这样，那么对字符串本身执行左移和右移操作将产生原始字符串。

作为另一种选择，我们可以遍历每个移动位置，看看是否有任何移动后的字符串与输入字符串匹配。

这两种情况下解决方案的时间复杂度都是O(n2)，其中n是字符串的长度。对任何字符串进行左移和右移都会得到给定的字符串。