查找也是後綴的前綴

Question

我正在尋找針對此問題的最佳解決方案。

給定一個string s of length n，找到一個從左到右的前綴，相當於從右到左的後綴。

前綴和後綴可以重疊。

示例：給定abababa，前綴爲[ababa]ba，後綴爲ab[ababa]。

我能夠得到以下在我的頭上，

1. 每個i = 0 to n-1，採取前綴結束在我和發現，如果我們有一個適當的後綴。現在是O(n^2)時間和O(1)空間。

2. 我想出了一個優化，我們索引所有字符的位置。這樣，我們可以從1 /中消除一組樣本空間。同樣，最壞的情況複雜度爲O(n^2)，額外的空間爲O(n)。

是否對此有任何更好的算法？

Answer 1

利用KMP算法。算法的狀態決定了「乾草堆的最長後綴仍然是針的前綴」。所以，只要把你的繩子作爲針和沒有第一個字符的繩子當乾草堆。在O(N)時間和O(N)空間運行。

與一些示例的實現：

public static int[] create(String needle) { 
    int[] backFunc = new int[needle.length() + 1]; 
    backFunc[0] = backFunc[1] = 0; 
    for (int i = 1; i < needle.length(); ++i) { 
     int testing = i - 1; 
     while (backFunc[testing] != testing) { 
      if (needle.charAt(backFunc[testing]) == needle.charAt(i-1)) { 
       backFunc[i] = backFunc[testing] + 1; 
       break; 
      } else { 
       testing = backFunc[testing]; 
      } 
     } 
    } 
    return backFunc; 
} 

public static int find(String needle, String haystack) { 
    // some unused character to ensure that we always return back and never reach the end of the 
    // needle 
    needle = needle + "$"; 
    int[] backFunc = create(needle); 
    System.out.println(Arrays.toString(backFunc)); 
    int curpos = 0; 
    for (int i = 0; i < haystack.length(); ++i) { 
     while (curpos != backFunc[curpos]) { 
      if (haystack.charAt(i) == needle.charAt(curpos)) { 
       ++curpos; 
       break; 
      } else { 
       curpos = backFunc[curpos]; 
      } 
     } 
     if (curpos == 0 && needle.charAt(0) == haystack.charAt(i)) { 
      ++curpos; 
     } 
     System.out.println(curpos); 
    } 
    return curpos; 
} 

public static void main(String[] args) { 
    String[] tests = {"abababa", "tsttst", "acblahac", "aaaaa"}; 
    for (String test : tests) { 
     System.out.println("Length is : " + find(test, test.substring(1))); 
    } 
} 

Answer 2

參見：

http://algorithmsforcontests.blogspot.com/2012/08/borders-of-string.html

用於O（n）的溶液

的代碼實際上計算的最後一個字符的索引中的前綴。對於實際的前綴/後綴，您將需要從0提取子到j個（包括兩端，長度爲j + 1）

Answer 3

簡單實現在C＃：

 string S = "azffffaz"; 

     char[] characters = S.ToCharArray(); 
     int[] cumulativeCharMatches = new int[characters.Length]; 
     cumulativeCharMatches[0] = 0; 

     int prefixIndex = 0; 
     int matchCount = 0; 

     // Use KMP type algorithm to determine matches. 

     // Search for the 1st character of the prefix occurring in a suffix. 
     // If found, assign count of '1' to the equivalent index in a 2nd array. 
     // Then, search for the 2nd prefix character. 
     // If found, assign a count of '2' to the next index in the 2nd array, and so on. 
     // The highest value in the 2nd array is the length of the largest suffix that's also a prefix. 
     for (int i = 1; i < characters.Length; i++) 
     { 
      if (characters[i] == characters[prefixIndex]) 
      { 
       matchCount += 1; 
       prefixIndex += 1; 
      } 
      else 
      { 
       matchCount = 0; 
       prefixIndex = 0; 
      } 

      cumulativeCharMatches[i] = matchCount; 
     } 

     return cumulativeCharMatches.Max();