Yaklaşık 6-8 saat Manacher algoritması sindirmek için uğraşıyorlar sonra, havlu atmaya hazırım. Ancak bunu yapmadan önce, burada karanlıkta son bir şans vardır: biri bunu açıklayabilir mi? Kodu umurumda değil. Birisi açıklamak istiyorumALGORİTMA.

Burada görünüyor Diğerleri algoritma açıklayan zevk gibiydi bir yer olması için: http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Dize dönüştürmek için istemenizi anlıyorum ki, '#bir#b#b#bir#abba Daha sonra ben kayboldum. Örneğin, daha önce sözü edilen yazar için algoritma önemli bir parçasıdır " der

                      if P[ i' ] ≤ R – i,
                      then P[ i ] ← P[ i' ]
                      else P[ i ] ≥ P[ i' ]. (Which we have to expand past 
                      the right edge (R) to find P[ i ])

Bu gibi yanlış, çünkü söylediği bir noktada O P[i] eşittir 5 P[ı'] = 7 ve P[i] değil daha az veya eşit için R - i.

Eğer algoritma biliyorsanız, burada biraz daha linkler: http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (Bu bir denedim, ama terminoloji korkunç ve kafa karıştırıcı. İlk olarak, bazı şeyler tanımlanmaz. Ayrıca, çok fazla değişken var. Değişken dir ne hatırlamak için bir kontrol listesi gerekir.)

Başka bir şeydir: http://www.akalin.cx/longest-palindrome-linear-time (iyi şanslar)

Algoritma temel özü doğrusal zaman en uzun palindrom bulmaktır. Çaba bir orta miktarda az O(n^2) yapılabilir. Bu algoritma oldukça "" onu almak için O(n). zeki olmalı

Mantık bağlantısı açıklama çok doğru olmadığını kabul ediyorum. Bazı ayrıntıları aşağıda veriyorum.

Manacher algoritması ne kadar palindrom ben uzanır merkezli içeren bir tablo P[i] doldurur. [5]=3, pozisyon beş iki tarafında üç karakterden sonra P ise palindrom bir parçası. Algoritma alır avantajı olması durumunda buldun uzun palindrom, sen-ebilmek doldurmak değerleri P sağ tarafta ise palindrom hızlı bir şekilde bakarak değerleri P sol yan, yana olmalılar çoğunlukla aynı.

Bahsettiğin durum açıklayarak başlayacağız, ve sonra gerektiği gibi, bu cevap genişleteceğim.

R palindrom C. merkezli sağ tarafında dizin Burada belirttiğiniz yerde devlet olduğunu gösterir:

C=11
R=20
i=15
i'=7
P[i']=7
R-i=5

ve mantığı böyle

if P[i']<=R-i:  // not true
else: // P[i] is at least 5, but may be greater

Pseudo-kod bağlantıyı gösteren P[i] olmalı sıfırdan büyük veya eşit P[ı'] eğer test başarısız olur, ama sanırım öyle olmalı sıfırdan büyük veya eşit R-ı ve açıklama desteklediğini söyledi.

Beri P[ı'] büyük R-ı, palindrom merkezli sana uzanan son palindrom merkezli C de bildiğimiz palindrom merkezli de olacağım en azından R-karakter, çünkü biz hala simetri için o noktaya kadar, ama biz arama açıkça ötesinde.

Eğer P[ı'] en başından beri hiçbir büyük R-ı, en büyük palindrom merkezli sana içinde en büyük palindrom merkezli C, ... bilinen P[i] olamaz herhangi bir büyük P[ben]. Eğer öyle olsaydı, bir çelişki olurdu. Olur yani böyle olması mümkün genişletmek palindrom merkezli ben ötesinde P[ben], ama mümkünse, o zaman biz de olması mümkün genişletmek palindrom merkezli sana bağlı simetri, ama zaten olması gerektiği gibi büyük olarak mümkün.

Bu durum daha önce gösterilmiştir:

C=11
R=20
i=13
i'=9
P[i']=1
R-i=7

Bu durumda, [ı']<=R-ı. P Hala 7 karakter palindrom kenarından uzak C merkezli olduğumuz için, en az 7 karakter etrafında etrafında 7 karakterleri de aynı olduğunu biliyoruz. Ben etrafında bir karakter bir palindrom, sadece' ben de, etrafında bir karakter bir palindrom vardır.

j_random_hacker mantığı bu şekilde daha fazla olması gerektiğini fark ettim:

if P[i']<R-i then
  P[i]=P[i']
else if P[i']>R-i then
  P[i]=R-i
else P[i]=R-i   expansion

[I'] < R-ı, [i]==P biliyoruz[ı'] hala palindrom içinde olduğumuza göre, merkezli C . P P

[I'] >P R-ben, o zaman aksi takdirde palindrom C merkezli R geçmiş uzun olurdu, çünkü[i]==R-P, biliyoruz

Yani genişleme[ı']==R-ı, Yani eğer P de palindrom[i] uzun olabilir bilmiyoruz. P gerçekten özel durumda gereklidir

Bu P[i]=min ayarlayarak gerçek kod işlenir (['] ı,R-ı P) ve her zaman genişleyen. Bunu yapmanın bu şekilde hiçbir genişleme gerekli ise, bu zaman genişlemesi yapmak için alınan sabit olduğu için zaman karmaşıklığı arttırmaz.