Checks whether left and right shifts of any string will result in the given string

A collection of

characters is represented by the string data type. It uses letters, numbers, symbols and spaces for logical arrangement. Most computer languages ​​use single or double quotes to enclose strings to distinguish them from other data types.

Programmers often use strings to perform some input and output operations, store and operate text data, etc. Some common operations on strings include concatenating (merging two or more strings), extracting substrings (getting a portion of a string), and searching for a specific character or pattern in a string.

method

We can use the following methods to determine whether the left shift and right shift results of a string are for each string −

Method 1. Brute force cracking method −

Method 2. Check substring −

Method 1: Brute force cracking method

Using the brute force method, generate all left and right shifts of the input string and compare each string with the target string. The time complexity of this method, where n is the length of the string, is O(n2).

grammar

Iterate through all possible left shifts and right shifts of the original string and compare them with the given string. This is to determine whether any left shift and right shift of the string will result in the given string. force method. The general syntax of this strategy is as follows −

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

algorithm

The brute force method of determining whether a left or right shift of a string results in a given string is to test every possible shift of the string and determine whether any one shift will fit the given string. The algorithm is as follows −

Step 1 − Initialize a variable to 0 at the beginning, indicating the current shift count.

Step 2 - When the shift number is less than the length of the string -

• Shift the string left, moving the first character to the end of the string.

• Verify that the shifted string matches the provided string. If there is a match, the true answer is given.

• Shift the string right by moving the last character to the beginning.

• Verify that the shifted string matches the provided string. If there is a match, give the true answer.

• Increase the shift count by 1.

Step 3 - After trying every possible shift, if no match is found, return false.

The Chinese translation of

Example 1

is:

Example 1

This implementation description function Shifted String receives two string parameters s and target, and returns a Boolean value result indicating whether target is a left or right shift of s.

Before determining whether the target is a shifted version of s, the function first confirms whether the lengths of the two strings are equal. After that, it builds a new string by combining the substrings before and after each possible shift position. This method returns true if the left or right shifted strings are similar in the desired string. If this is not the case, return false.

In the main function, we define two example strings s and target, and use these strings to call the Shifted String method. The program then indicates whether target is the shifted form of 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;
}

Output

The string is shifted.

Method 2: Check substring

To determine whether a smaller string is part of a longer string, you can use the "check substring" method. This process involves comparing individual substrings of the same length as the smaller string to the smaller string itself while iterating over the longer string. If two strings match, this confirms that the shorter string is indeed a subset of the larger text. To add complexity and variation in sentence length to the essay, the idea should be broken down into simple yet engaging parts.

grammar

The following syntax can be used to determine whether left and right shifts of any string result in the supplied string -

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

algorithm

The following algorithm is used to determine whether left and right shifts of a string produce the supplied string −

Step 1 - Start typing the input string and target string.

Step 2 - Verify that the length of the input string and the length of the target string are equal. If not equal, False is returned.

Step 3 − To build a new sequence, the input string must be merged with the output string.

Step 4 - A comparison is required to confirm whether the input string is included in the newly constructed sequence.

Step 5 - If the two strings are exactly the same, the answer will be unquestionable; otherwise, the answer will be no.

The Chinese translation of

Example 2

is:

Example 2

This is a C code used to determine whether shifting left and right of any string will produce a given string -

此示例研究了两个数组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和任何字符串的右移都会导致给定的字符串−

The above is the detailed content of Checks whether left and right shifts of any string will result in the given string. For more information, please follow other related articles on the PHP Chinese website!