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

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

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

方法

我们可以使用以下方法来确定字符串的左移和右移结果是否为每个字符串−

方法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，表示当前的移位计数。

第二步 - 当移位数小于字符串长度时 -

• 将字符串左移，将第一个字符移到字符串的末尾。

• 验证移位后的字符串是否与提供的字符串匹配。如果匹配，则给出真实答案。

• 通过将最后一个字符移到开头，对字符串进行右移。

• 验证移位后的字符串与提供的字符串是否匹配。如果匹配，给出真答案。

• 将移位计数增加1。

第三步 - 在尝试了每个可能的移位后，如果没有找到匹配，则返回false。

Example 1

的中文翻译为：

示例 1

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

在确定目标是否是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.

方法二：检查子字符串

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

语法

以下语法可用于确定任何字符串的左移和右移是否导致提供的字符串 -

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 − 要构建一个新的序列，输入字符串必须与输出字符串合并。

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

步骤 5 - 如果两个字符串完全相同，则答案将是不容置疑的；相反，答案将是否定的。

Example 2

的中文翻译为：

示例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是字符串的长度。ft和任何字符串的右移都会导致给定的字符串−

以上是检查任意字符串的左移和右移是否会得到给定的字符串的详细内容。更多信息请关注PHP中文网其他相关文章！