檢查任何字串的左移和右移是否會得到給定的字串

---

字串資料型別由字元集合表示。它使用字母、數字、符號和空格進行邏輯排列。大多數計算機語言使用單引號或雙引號括起字串，以將其與其他資料型別區分開來。

程式設計師經常使用字串執行一些輸入和輸出操作、文字資料的儲存和操作等。字串上的一些常見操作包括連線（組合兩個或多個字串）、子字串提取（獲取字串的一部分）以及在字串中搜索特定字元或模式。

方法

我們可以使用以下方法來確定字串的左移和右移是否會得到每個字串：

方法 1. 暴力法

方法 2. 檢查子字串

方法 1：暴力法

使用暴力法，生成輸入字串的所有左移和右移，然後將每個與目標字串進行比較。此方法的時間複雜度為 O(n2)，其中 n 是字串的長度。

語法

確定任何字串的左移和右移是否會得到給定字串的暴力法是遍歷原始字串的所有可能的左移和右移，並將它們與給定字串進行比較。此策略的通用語法如下：

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 - 當移位次數小於字串長度時：

• 將字串左移，即將第一個字元移到字串的末尾。

• 驗證移位後的字串是否與給定字串匹配。如果匹配，則返回真。

• 對字串應用右移，即將最後一個字元移到開頭。

• 驗證移位後的字串是否與給定字串匹配。如果匹配，則返回真。

• 將移位計數增加 1。

步驟 3 - 如果在嘗試所有可能的移位後沒有找到匹配項，則返回假。

示例 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 - 如果兩個字串完全一致，則答案將是肯定的；否則，答案將是否定的。

示例 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 是字串的長度。任何字串的左移和右移是否會得到給定字串：