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

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

程式設計師經常使用字串來進行一些輸入和輸出操作，儲存和操作文字資料等。字串的一些常見操作包括拼接（將兩個或多個字串合併）、提取子字串（獲取字串的一部分）以及在字串中搜尋特定字元或模式。

方法

我們可以使用以下方法來確定字串的左移和右移結果是否為每個字串−

方法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中文網其他相關文章！