將字符串表示爲子字符串的某些功能

給定一個字符串，我們必須檢查一個字符串是否可以用重複某些有限時間的子字符串表示。將字符串表示爲子字符串的某些功能

ABABAB - >（AB）^ 3

我看到了一個解決方案，說先找到最長適當的前綴，這也是一個後綴。讓這個前綴的長度爲k。設n是原始字符串的長度。如果n％（n-k）== 0，則字符串可以表示爲子字符串重複的有限次數。否則，沒有。

我無法理解此解決方案背後的邏輯。任何人都可以解釋爲什麼這個解決方案有效嗎鏈接，我看到了這個解決方案：geeksforgeeks

來源

2016-06-27 Shivam Mitra

說明在那裏給出，鏈接你已經給出，也有圖表。你需要什麼更好的解釋？ – vish4071

我無法理解它。我想要一個廣義的證明。 –

好吧，所以首先，讓我們調用形成input字符串A的子字符串。所以，

input = A^a (with a is constant)

我們可以看到，最長適當的前綴，這也是一個後綴應該包括input的至少一半，如果input是電源線。該證明是簡單

如果a是偶數，情況實在是微不足道。
如果a是奇數，所以input = (A^b)A(A^b)，我們可以看到，最長前綴後綴應該至少(A^b)A (with b = (a - 1)/2)

所以，現在，讓我們考慮三種情況：

如果前綴後綴的長度爲k爲k < n/2，那麼n - k > n/2→n % (n - k) != 0，如上所述，該字符串不能是電源字符串。
如果前綴後綴的長度爲k是k = n/2 - >這種情況很簡單。
如果前綴後綴的長度k是k > n/2，所以，我們可以可視化輸入字符串作爲
```
input = ACA 
```
隨着C是前綴和後綴之間的重疊區域，並且如前綴和後綴是基本持平，我們可以看到，
```
AC = CA 
```
我們假定C > A長度，爲了AC = CA，因此，我們可以把ç爲C = A + B - >A + A + B = A + B + A，日只有在A == B時纔會發生。

因此，輸入的格式爲input = AAAA，這顯然是一個電源字符串。在C = A的情況下，我們有input = AAA，案例C < A可以證明與案例C > A類似。

來源

2016-06-27 15:51:13

很好解釋。無法做得更好。 – vish4071

如果n％（n-k）== 0，則該字符串可以表示爲子字符串重複的有限次數。否則，沒有。這個說法在算法中非常有用，所以我們首先證明它。
如果nk是後綴的長度，那麼如果n％（nk）！= 0 n將等於q長度= nk的串的串聯和串長度爲未成年人NK（q = N /（NK））
因此n在這種情況下不能後綴的平方
推理由反對派領導
現在讓我們寫代碼

class Program 
    { 
     static void Main(string[] args) 
     { 
      string myString = "abab"; 
      int k = suffixLentgth(myString); 
      if (k > 0) 
      { 
       Console.WriteLine(myString.Substring(k, myString.Length - k)); 
      } 

     } 
     static int suffixLentgth(string ch) 
     { 
      int n = ch.Length; 
      for (int i = 2; i < n; i++) 
      { 
       bool isPower = true; 
       if (n % (n - i) == 0) // this suffix can fulfil your dreams 
       { 
        for (int j = 0; j < (n/(n - i)) - 1; j++) 
        { 
         if (ch.Substring((n - i) * j, n - i) != ch.Substring((n - i) * (j + 1), n - i)) 
         { 
          isPower = false; 
          break; 
         } 
        } 
        if (isPower) 
         return i; 
       } 
      } 
      return 0; 
     }

來源

2016-06-27 15:52:41 AnotherGeek

將字符串表示爲子字符串的某些功能

回答

相關問題