確定一個字符串在O（n）時間內有多少次旋轉與原始字符串匹配？

有很多問題討論旋轉字符串或確定一個字符串是否是另一個字符串的旋轉的最快/最佳方式。確定一個字符串在O（n）時間內有多少次旋轉與原始字符串匹配？

例如，忽略輸入消毒，你會看到something like this爲IsRotation：

public static bool IsRotation(string s1, string s2) 
{ 
    return (s1.Length == s2.Length && (s1 + s1).IndexOf(s2) != -1); 
}

而且像這樣的東西旋轉：

public static string Rotate(string s, int index) 
{ 
    //Can't rotate. Return input. 
    if (s.Length < 2) 
    { 
     return s; 
    } 

    // Break input in half at rotation index 
    var s1 = s.Substring(0, index); 
    var s2 = s.Substring(index); 

    // Reverse the halves 
    var s1Reversed = Reverse(s1); 
    var s2Reversed = Reverse(s2); 

    // Join the reversed halves 
    var joined = s1Reversed + s2Reversed; 

    //Reverse and return the result. 
    var rotated = Reverse(joined); 
    return rotated; 
}

例如，使用「富... 「旋轉（」foo「，1）==」ofo「 - 和 - IsRotation（」foo「，」ofo「）== true;

我的問題是這些問題的延伸。

給定一個輸入字符串s，確定該字符串的旋轉次數與原始字符串相同。

考慮輸入字符串作爲旋轉，一些樣品輸入/輸出對：

IdenticalRotationCount("") == 1 
IdenticalRotationCount("s") == 1 
IdenticalRotationCount("sa") == 1 
IdenticalRotationCount("ss") == 2 
IdenticalRotationCount("ByeBye") == 2 
IdenticalRotationCount("StackOverflow") == 0

我被告知存在將爲O運行（n）的時間的解決方案。初學者的解決方案是這樣的：

public static int IdenticalRotationCount(this string s) 
{ 
    //If length of s is less than two, we cannot rotate. Return 1. 
    if (s.Length < 2) 
    { 
     return 1; 
    } 

    //Get first char in s 
    var first = s[0]; 

    //Consider input as first rotation that matches 
    var count = 1; 

    //Try each rotate position 
    for (var i = 1; i < s.Length; ++i) 
    { 
     var c = s[i]; 

     //If current character doesn't start with same character as input 
     //we can skip the rotation 
     if (c != first) 
     { 
      continue; 
     } 

     //If the rotation at index i equals the input string, add 1 to result 
     if (StringExtensions.Rotate(s, i) == s) 
     { 
      ++count; 
     } 
    } 

    return count; 
}

但是，如果你選擇一個荒謬的輸入，像200000個連續的「一的，它會在相當一段時間運行。

任何人都可以提供運行在O（n）時間的解決方案嗎？在旋轉之前將輸入分成兩半時，我可以通過做實際比較來看到N^2，而不是做實際的旋轉，但看不到如何做O（n）。

謝謝！

PS - 如果有更合適的方式發佈這類問題，請在評論中說明。我很樂意移動它。

來源

2013-05-02 Eric Burcham

不應該IdenticalRotationCount（「StackOverflow」）== 1？因爲每個字符串都是自己的旋轉 – faisal 2013-05-03 00:03:47

@faisal - 好吧，不一定。但是夠公平的;我應該指定。 – 2013-05-29 19:29:40

這引發了思考 - 考慮問題「如果我連接原始字符串與自己，什麼是連接結果中的原始字符串的第一個索引」。有一點想法，它看起來好像它會回答問題O（n）。

E.g. 原始字符串「ByeBye」級聯字符串「ByeByeByeBye」

原始字符串出現在級聯字符串中從（0開始）索引2處。這告訴你一些事情。

來源

2013-05-02 23:21:18

假設字符串是'n''a's後跟一個'b'（這樣每次旋轉都是唯一的）。在'n-i'位置上''第''測試將失敗，所以字符比較的總數將是'O（n^2）'。 – rici 2013-05-02 23:28:46

@rici - 真，低估了確定連結中原始位置的成本。 D'哦。 – 2013-05-03 13:03:03

如果一個字符串等於它自己的偏移量爲k並且沒有更小的偏移量，那麼該字符串必須重複其長度爲k的前綴。這也將等於它的旋轉的所有倍數k，所以將精確地爲n/k這樣的旋轉，其中n是字符串的長度。這很容易證明。

確實有一個O(n)算法來確定k的值。一種方法是使用Duval算法進行Lyndon因式分解（請參閱Wikipedia）。這只是一個暗示;如果需要，我會看看是否可以生成一些實際的僞代碼。

來源

2013-05-03 00:00:06 rici

確定一個字符串在O（n）時間內有多少次旋轉與原始字符串匹配？

回答

相關問題