JavaScript程式：檢查字串是否互為旋轉字串

---

字串互為旋轉字串意味著兩個字串可以透過向右或向左旋轉得到另一個字串。向右旋轉時，字串的字元移到其下一個索引，而對於第零個索引，它取最後一個索引的字元（假設字串是一個環）。左旋轉類似於右旋轉，但方向相反。我們將得到兩個字串，我們必須找到是否可以透過旋轉字串的字元來得到另一個字串。

輸入

string1: “abcdef” 
string2: “cdefab”

輸出

Yes

解釋：我們可以將第一個字串向左旋轉兩次得到第二個字串。第一次旋轉後，String1 將變為“bcdefa”，第二次旋轉後，它將與第二個字串相同。

輸入

String1: “abcdef”
String2: “bcadef” 

輸出

No

解釋 - 我們可以旋轉一個字串或陣列的最大旋轉次數（而不得到原始字串）等於給定字串或陣列的長度。

這裡，在六次旋轉後，我們無法從字串1得到字串2，證明不可能在最大旋轉次數後使兩個字串相等。

樸素方法

在這種方法中，我們將只旋轉給定字串的長度次數，並與另一個給定字串匹配。

示例

// function to rotate the string in the left direction 
function left_rotate(str){

   // splitting the string and then again joining back 
   str = str.substr(1) + str.substr(0,1);
   return str;
}

// function to check if one string is equal to another after certain rotations
function check(str1, str2){

   // checking the size of both strings 
   if(str1.length != str2.length){
      return false;
   } 
   var k = str1.length
   while(k--){
      if(str1 == str2){
         return true;
      }
      str1 = left_rotate(str1);
   }
   return false;
}

// defining the strings
var str1 = "abcdef" 
var str2 = "cdefab"
console.log("The given strings are " + str1 + " and " + str2);

// calling the function 
if(check(str1,str2)){
   console.log("Yes, we can obtain the second string from the given string by rotating it.");
} else{
   console.log("No, we cannot obtain the second string from the given string by rotating it.");
}

// defining the strings
str1 = "abcdef" 
str2 = "bacdef"
console.log("The given strings are " + str1 + " and " + str2);

// calling the function 
if(check(str1,str2)){
   console.log("Yes, we can obtain the second string from the given string by rotating it.");
} else{
   console.log("No, we cannot obtain the second string from the given string by rotating it.");
}

輸出

The given strings are abcdef and cdefab
Yes, we can obtain the second string from the given string by rotating it.
The given strings are abcdef and bacdef
No, we cannot obtain the second string from the given string by rotating it.

時間和空間複雜度

上述程式碼的時間複雜度為 O(N*N)，其中 N 是給定字串的大小。

上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何空間。

KMP演算法

在這個程式中，我們將使用 KMP 演算法來查詢旋轉，讓我們來看程式碼。

示例

// function to check if one string is equal to another using KMP
function check(str1, str2){

   // checking the size of both strings 
   if(str1.length != str2.length){
      return false;
   } 
   var len = str1.length;
   
   // create lps that will hold the longest prefix
   var lps = Array.from({length: len}, (_, i) => 0);
   
   // length of the previous longest prefix suffix
   var len_p = 0;
   var i = 1;
   lps[0] = 0; 
   
   // the loop calculates lps[i] for i = 1 to n-1
   while (i < len) {
      if (str1.charAt(i) == str2.charAt(len_p)) {
         lps[i] = ++len_p;
         i++;
      } else {
         if (len_p == 0) {
            lps[i] = 0;
            i++;
         } else {
            len_p = lps[len_p - 1];
         }
      }
   }
   i = 0;
   
   // match from that rotating point
   for(var k = lps[len - 1]; k < len; k++) {
      if (str2.charAt(k) != str1.charAt(i++)){
         return false;
      }
   }
   return true;
}

// defining the strings
var str1 = "abcdef" 
var str2 = "cdefab"
console.log("The given strings are " + str1 + " and " + str2);

// calling the function 
if(check(str1,str2)){
   console.log("Yes, we can obtain the second string from the given string by rotating it.");
} else{
   console.log("No, we cannot obtain the second string from the given string by rotating it.");
}

// defining the strings
str1 = "abcdef" 
str2 = "bacdef"
console.log("The given strings are " + str1 + " and " + str2);

// calling the function 
if(check(str1,str2)){
   console.log("Yes, we can obtain the second string from the given string by rotating it.");
} else{
   console.log("No, we cannot obtain the second string from the given string by rotating it.");
}

輸出

The given strings are abcdef and cdefab
Yes, we can obtain the second string from the given string by rotating it.
The given strings are abcdef and bacdef
No, we cannot obtain the second string from the given string by rotating it.

時間和空間複雜度

對於上述程式，時間和空間複雜度均為 O(N)。我們使用了額外的空間來儲存 lps 陣列中的值。

結論

在本教程中，我們實現了一個 JavaScript 程式來檢查我們是否可以透過向左或向右旋轉字串的字元來從另一個給定字串獲得一個給定字串。我們使用了樸素方法，其時間複雜度為 O(N*N)，空間複雜度為 O(1)。此外，我們還實現了具有 O(N) 時間和空間複雜度的 KMP 演算法。