檢測一系列字符何時重複比O（n！）更好

我需要找出一系列字符（實際上是一個很長的數字）何時開始重複。我認爲一個模式將是最簡單的。誰能幫我？檢測一系列字符何時重複比O（n！）更好

2011-04-21 Deho

最簡單的方法是強行它，但然後你的運行時間是O（n！） – austinbv 2011-04-21 01:14:30

是的，它的方式太長時間蠻力:)我試過 – Deho 2011-04-21 01:15:10

可能有類似的問題。 http://download.oracle.com/javase/1.5.0/docs/api/java/util/regex/Matcher.html#find%28%29 – Tass 2011-04-21 01:19:30

如果它是一個數字，則從最後開始。

查找最後一個n和第二個最後一個n數字相同的序列，該數字在最大數字位數上重複。 O（n）

重複序列停止（來自結尾），即重複開始的位置。

例如說你有1.2340111101111

你可以看到1重複，但只有4位數。 01111重複10位數字表示重複開始後1.234

來源

2011-04-21 08:32:05

取決於這個序列來自何處，this might be useful。

來源

2011-04-21 01:55:54 hammar

我不知道Java。我不確定你確切的問題，但似乎你試圖找到一個序列的最大軌道。下面的僞代碼應有助於：

Given sequence M of length N 
Initialize list of indices K 
foreach index i from N-1 to N/2 
    seqLength := N-i 
    isOrbit? := true 
    foreach index s from 0 to seqLength-1 
     if M[N-1-s] != M[N-1-seqLength-s] then 
      isOrbit? := false 
    if isOrbit? then 
     append(K, i)

最長軌道是，當然，最後的入口加入到K的算法是O（n^2/4）左右。它本質上是一種改進的子序列搜索算法。

來源

2011-04-29 23:22:56 thechao

這是相當書呆子 – Ethan 2011-04-29 23:48:57

@Ethan，這可能不是書呆子交換，但他因爲爲提問者提供良好的搜索飼料而得到讚賞。 – 2011-04-30 00:13:24

檢測一系列字符何時重複比O（n！）更好

回答

相關問題