SORU
12 Temmuz 2009, Pazar


Belirli bir dize en uzun palindrom döndüren bir fonksiyon yazın

e.""dizesinde "" . abaccddccefe ccddcc g

O(n^2) zaman çalışır ama bir çözüm düşündüm

Algo 1:

Adımlar: Kaba kuvvet yöntemi

  1. Döngüler için 2
    i = 1 i dizi daha az.uzunluğu -1
    j j=1 için daha az dizi daha.uzunluğu
  2. Bu şekilde diziden mümkün olan her kombinasyonu dize alabilirsiniz
  3. Eğer string bir palindrom olup olmadığını denetler olan palindrom bir işlevi var
  4. (ı,j) her dize için bu bir dize değişkenine palindrom bir dükkan ise işlevini çağırın
  5. Eğer mevcut olandan daha büyük ise bir sonraki palindrom alt bulursanız ve, akım ile değiştirin.
  6. Nihayet dize değişkeni cevabı olacak

Konular: 1. Bu algo O(n^2) zaman içinde çalışır.

Algo 2:

  1. Dize ters ve farklı dizi içinde saklayın
  2. Şimdi bulmak her iki dizi arasındaki en büyük eşleşen alt dize
  3. Ama bu da O(n^2) zaman içinde çalışır

Daha iyi bir zamanda çalışan bir algo düşünebiliyor musunuz. Mümkün O(n) zaman

CEVAP
26 EKİM 2013, CUMARTESİ


Uzun, palindrom O(n) Manacher's Algorithm kullanarak bulabilirsiniz! Uygulanması here here bulunabilir.
Giriş için String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE". 1234567887654321 olan doğru çıkış bulur.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Darren Kitchen

    Darren Kitch

    3 EKİM 2011
  • Jared Busch

    Jared Busch

    25 Mayıs 2011
  • Kyletiv7

    Kyletiv7

    28 Mayıs 2007