Longest Common Substring
İki dize, s1 ve s2 alırsın. Alt dize, bir dizgeden alınan ve kesintisiz devam eden harf dizisidir; örneğin clockwork içindeki ork. s1 ve s2'nin ortak olarak içerdiği en uzun alt dizeyi bul ve uzunluğunu döndür. Her iki dizgede de ortak bir harf yoksa yanıt 0'dır.
Fonksiyon
- s1string
- ilk dize
- s2string
- ikinci karakter dizisi
- Döndürürinteger
- her iki dizgede de bulunan en uzun harf bloğunun uzunluğu
Kısıtlar
1 ≤ s1.length ≤ 10001 ≤ s2.length ≤ 1000s1ves2küçük İngilizce harflerden oluşur.
Örnekler
- Girdi
- s1 = "clockwork"s2 = "workshop"
- Çıktı
- 4
- Açıklama
work,clockwork'ü kapatıpworkshop'u açar; dolayısıyla uzunluğu 4 olan ortak bir alt dizgedir ve her ikisinde de daha uzun bir blok bulunmaz.
- Girdi
- s1 = "hammer"s2 = "harmed"
- Çıktı
- 2
- Açıklama
havemeher iki kelimede de geçer, ancak üç harften oluşan hiçbir dizi geçmez. Her iki kelime de h, a, m, e harflerini bu sırayla içerir, ancakharmedsözcüğünde a ile m arasında r vardır.
- Girdi
- s1 = "fig"s2 = "plum"
- Çıktı
- 0
- Açıklama
- İki sözcüğün ortak harfi yoktur; bu nedenle en uzun ortak alt dize boştur ve uzunluğu 0'dır.
Ek soru
Verilen L uzunluğunda ortak bir alt dizenin kayan özet kullanılarak yaklaşık O(n + m) sürede var olup olmadığını test edebilir ve ardından L üzerinde ikili arama yapabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Her başlangıç konumu çiftini karşılaştırmak işi tekrarlar:
ivejkonumlarında başlayan blok,i+1vej+1konumlarında başlayan bloğu içerir. Birinin yanıtını diğeri için yeniden kullanmayı dene.Her konum çifti için daha dar kapsamlı bir soru sor: tam olarak
s1[i]ves2[j]konumlarında biten ortak blok ne kadar uzun? İki harf farklıysa sonuç 0'dır. Eşleşiyorlarsa sonuç, onlardan önceki iki harf için bulunan yanıttan bir fazladır.Boş önekler için 0. satırı ve 0. sütunu kullanarak tabloyu
run[i][j]uzunluklarıyla doldurun. Yanıt, son hücre değil, tablonun herhangi bir yerindeki en büyük değerdir. Her hücre yalnızca çapraz olarak yukarı ve sola komşu hücreyi okur; bu nedenle sağdan sola ilerlenen tek bir satır yeterlidir.
Çözüm
Her başlangıç çifti için eşleşmeyi genişletmek aynı harfleri yeniden okur. Bunun yerine bloğun nerede bittiğine bakın: s1[i] ve s2[j] konumlarında biten ortak blok, bu konumlardan bir önceki iki harfte biten bloktan bir harf daha uzundur ya da harfler farklıysa boştur. Bu uzunluklardan oluşan bir tablo O(n × m) süresinde yanıt verir.
Her başlangıç konumu çiftinden genişlet
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her ortak alt dize, s1 içinde bir i konumunda ve s2 içinde bir j konumunda başlar. Her ikili için harfler eşleştiği sürece ileri doğru ilerleyip adımları say; en büyük sayı cevaptır.
Tekrarlayan metin, ilerlemelerin uzun sürmesine neden olur. Her iki dize de a harfinin 1000 kopyasından oluştuğunda, her ikili daha kısa son ekin sonuna kadar ilerler: yaklaşık 3.3 × 10^8 harf karşılaştırması. (i, j) konumundan başlayan ilerleme, bir harf ilerideki (i+1, j+1) konumundan başlayan ilerlemenin tamamını tekrarlar.
Algoritma
best = 0değerini ata.s1içindeki herives2içindeki herjiçink = 0değerini ata.- Hem
i+khem dej+kkendi dizelerinin içindeyken ves1[i+k] == s2[j+k]koşulu sağlanırken,kdeğerini 1 artır. - En büyük
kdeğerinibestiçinde tut ve bunu döndür.
def longestCommonSubstring(s1, s2):
n, m = len(s1), len(s2)
best = 0
for i in range(n):
for j in range(m):
# Walk forward while the two strings agree
k = 0
while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
k += 1
if k > best:
best = k
return bestHer bir çiftte sona eren blok uzunlukları tablosu
Sezgi
run[i][j], s1[i-1] ve s2[j-1] konumlarında tam olarak sona eren en uzun ortak bloğun uzunluğu olsun; 0. satır ve 0. sütunda 0 bulunur. Böyle bir blok her iki harfi de içermelidir. Harfler farklıysa blok yoktur ve hücre 0'dır. Eşleşiyorlarsa blok, bu ikiliden ve her iki dizgede de bir harf önce sona eren bloktan oluşur: run[i-1][j-1] + 1. Her ortak alt dize bir yerde sona erdiğinden, yanıt nerede olursa olsun en büyük hücredir.
hammer ve harmed için h'ler 1 verir, a'lar bunu 2'ye çıkarır, ardından r bloğu keser. hammer'daki ikinci m, m ile r'nin uyuşmamasından sonra harmed'daki m ile eşleşir; bu nedenle 1'den başlar ve e'ler bunu 2'ye çıkarır. Hiçbir hücre 3'e ulaşmaz.
Her hücre için bir karşılaştırma: 1000 harfli iki dize için, metin ne olursa olsun, yaklaşık bir milyon.
Algoritma
rundeğişkenine, hepsi 0 olann+1satır vem+1sütun ayır vebest = 0olarak ayarla.ideğerini 1..naralığında döngüye sok ve bunun içindejdeğerini 1..maralığında döngüye sokaraks1[i-1]iles2[j-1]değerlerini karşılaştır.- Eşleşme varsa
run[i][j] = run[i-1][j-1] + 1olarak ayarla vebestdeğerini güncelle. - Eşleşme yoksa hücreyi 0 olarak bırak.
bestdeğerini döndür.
def longestCommonSubstring(s1, s2):
n, m = len(s1), len(s2)
# run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
run = [[0] * (m + 1) for _ in range(n + 1)]
best = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i - 1] == s2[j - 1]:
run[i][j] = run[i - 1][j - 1] + 1
if run[i][j] > best:
best = run[i][j]
# a mismatch leaves run[i][j] at 0
return bestSağdan sola güncellenen tek satır
Sezgi
Her hücre yalnızca çapraz olarak yukarıdaki ve soldaki hücreyi okur. Bu nedenle, j değerlerini sağdan sola ziyaret edersen, m+1 sayıdan oluşan tek bir run dizisi tabloyu tutabilir: run[j] değerini yazdığında, run[j-1] yuvası hâlâ s1 dizisindeki önceki harfe ait değeri tutar; bu da çapraz hücredir.
Artık eşleşmeme durumunda açıkça 0 yazılmalıdır, çünkü yuva hâlâ önceki satırdan bir sayı tutmaktadır. Zaman karmaşıklığı O(n × m) olarak kalır ve bellek kullanımı yaklaşık 10^6 sayıdan 1001'e düşer.
Algoritma
m+1sıfırdan oluşan birrundizisi oluştur vebest = 0olarak ayarla.s1dizisindeki herchharfi için,jdeğerinim'den 1'e kadar geriye doğru ilerlet.ch == s2[j-1]iserun[j] = run[j-1] + 1olarak ayarla vebestdeğerini güncelle.- Aksi takdirde
run[j] = 0olarak ayarla. bestdeğerini döndür.
def longestCommonSubstring(s1, s2):
m = len(s2)
# run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
run = [0] * (m + 1)
best = 0
for ch in s1:
# Right to left, so run[j-1] still holds the value from the previous letter of s1
for j in range(m, 0, -1):
if ch == s2[j - 1]:
run[j] = run[j - 1] + 1
if run[j] > best:
best = run[j]
else:
run[j] = 0
return best
Tuzaklar ve uç durumlar
- Son hücreyi döndürmek.
run[n][m]yalnızca iki dizenin de son harflerinde biten blokları kapsar.abcveabdiçin sonuç 0 iken,abiçin 2 olur. - Uyuşmazlıkta daha büyük komşu değeri kopyalamak. Bu, alt dizi kuralıdır ve bir bloğun harfleri atlamasını sağlar:
hammerveharmediçin 2 yerine 4 bildirir. - Tek satırda soldan sağa ilerlemek. Çapraz değer, siz onu okumadan üzerine yazılır; bu nedenle
aileaakarşılaştırıldığında sonuç 2 olur. - Tek satırda sıfırlamayı atlamak.
s1dizgesindeki önceki harften kalan uzunluk korunur ve daha sonra orada bulunmayan bir bloğu genişletir. - Kaba kuvvet yönteminde sınır denetimi yapmadan ilerlemek.
zzzzilezzkarşılaştırıldığında, daha kısa dizgenin sonunu aşarak okuma yapar.
Sıkça sorulan sorular3
En uzun ortak alt dize ile en uzun ortak alt dizi arasındaki fark nedir?
Alt dize, kesintisiz bir harf dizisidir; alt sıra ise sıralamayı korur ancak aralarda boşluk bırakabilir. hammer ve harmed için en uzun ortak alt dizenin uzunluğu 2, en uzun ortak alt sıranın uzunluğu ise 4'tür (hame). Tablolarda, eşleşmeme alt dize hücresini 0'a sıfırlar; alt sıra hücresinin ise daha büyük komşu hücredeki değeri kopyalamasını sağlar.
En uzun ortak alt dizenin zaman karmaşıklığı nedir?
Dinamik programlama çözümü O(n × m) zaman ve tek bir satırla O(m) bellek gerektirir. Her başlangıç çifti için genişletme, en kötü durumda O(n × m × min(n, m)) zaman alır. Bir sonek otomatı, çok daha uzun bir program pahasına yaklaşık O(n + m) karmaşıklığına ulaşır.
En uzun ortak alt dizenin kendisini nasıl döndürürsünüz?
Bir hücre best değerini her aştığında, o bloğun bittiği s1 içindeki i konumunu da kaydet. Sonunda alt dize, orada biten s1 içindeki best harftir. Kesin büyüktür karşılaştırması, s1 içinde bulunan en uzun ilk bloğu korur.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def longestCommonSubstring(s1, s2):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
s1 = "clockwork" s2 = "workshop"
Beklenen Çıktı
4