Find the First Occurrence in a String

Q: Bir dizenin ilk geçtiği yeri bulmanın zaman karmaşıklığı nedir?

Her başlangıç konumunu kontrol etmek, en kötü durumda O(n · m) zaman alır; burada n ve m , haystack ve needle uzunluklarıdır ve O(1) ek alan kullanır. Knuth-Morris-Pratt algoritması, harfler ne olursa olsun O(n + m) zaman alır ve tablosu için O(m) alan kullanır.

KolayDiziler ve dizgiler İki işaretçi

+10

Sana haystack ve needle adında iki dize veriliyor. needle ifadesinin ilk geçtiği yerin haystack içindeki indeksini 0'dan başlayarak döndür. needle, haystack içinde hiç geçmiyorsa -1 döndür. find veya indexOf gibi yerleşik bir alt dize arama işlevini çağırmak yerine aramayı kendin yaz.

Fonksiyon

strStr(haystack: string, needle: string) → integer

haystackstring: içinde arama yapılacak metin
needlestring: aranacak dize
Döndürürinteger: needle'ın ilk kopyasının başladığı dizin ya da hiç yoksa -1

Kısıtlar

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Her iki dize de yalnızca küçük İngilizce harfler içerir.
needle, haystack'den daha uzun olabilir. Bu durumda içinde yer alamaz ve cevap -1 olur.

Örnekler

Girdi: haystack = "bananarama"needle = "ana"
Çıktı: 1
Açıklama: 1, 2 ve 3 indekslerindeki harfler ana sözcüğünü oluşturur. İkinci bir kopya 3. indekste başlar ve ilk kopyayla örtüşür, ancak cevap ilk kopyadır; dolayısıyla cevap 1'dir.

Girdi: haystack = "pineapple"needle = "apples"
Çıktı: -1
Açıklama: apple 4. indekste başlar ve arama metni hemen ardından biter; bu nedenle aranan dizenin son s harfinin eşleşebileceği bir harf yoktur. apples dizisinin tamamı bulunmadığından yanıt -1 olur.

Girdi: haystack = "abcabcabd"needle = "abcabd"
Çıktı: 3
Açıklama: 0 indeksindeki deneme beş harfle eşleşir: abcab; ardından, aranan dizenin d istediği yerde bir c ile karşılaşır. Eşleşen kopya 3 indeksinde başlar ve son d ile biter.

Gönderirken +16 gizli test

Ek soru

needle'ın başladığı tüm indeksleri, çakışan kopyalar da dahil olmak üzere, yine O(n + m) zamanda döndürebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

needle değerini her başlangıç konumunda karşılaştırmak doğrudur, ancak eşleşmeler neredeyse başarılı olduğunda yavaştır: sonuna yakın bir yerde başarısız olan uzun bir kısmi eşleşme atılır ve sonraki başlangıçta aynı harflerin çoğu yeniden okunur. Knuth-Morris-Pratt algoritması bu işi korur. Yalnızca needle kullanılarak oluşturulan bir tablo, başarısız bir kısmi eşleşmenin ne kadarının hâlâ kullanılabileceğini belirtir; böylece tarama haystack içinde asla geriye gitmez ve O(n + m) sürede tamamlanır.

Her başlangıç konumunu kontrol et

Doğru, ama en büyük testlerde bitmiyor

Sezgi

haystack için uzunluğa n, needle için m diyelim. needle kopyası 0 ile n-m arasındaki herhangi bir indiste başlayabilir. Bu başlangıçları soldan sağa deneyin. Her birinde needle ile haystack'i harf harf karşılaştırın ve ilk farklılıkta durun. Tüm m harfin eşleştiği ilk başlangıç yanıttır; soldan sağa ilerlemek, bunun ilk kopya olmasını sağlar.

Son başlangıç n-m olur; çünkü daha sonra başlayan bir kopya haystack'in sonunu aşar. Aynı sınır, needle haystack'ten uzun olduğunda da işe yarar: denenecek başlangıç yoktur ve döngü -1 sonucuna ulaşır.

Maliyet, harflerin çoğu eşleştiğinde ortaya çıkar. 50.000 adet a içeren bir haystack ve ardından bir b gelen 24.999 adet a içeren bir needle ele alalım. 25.001 başlangıcın her birinde, b'ye ulaşmadan önce 25.000 harf karşılaştırılır; bu da -1 yanıtı için 6 × 10^8'den fazla karşılaştırma demektir.

Algoritma

n ve m, haystack ve needle uzunlukları olsun.
0'dan n-m'ye kadar her start için j'yi 0 olarak ayarla.
j < m olduğu ve haystack[start + j], needle[j]'ye eşit olduğu sürece j'yi artır.
j, m'ye ulaştıysa tüm harfler eşleşmiştir: start değerini döndür.
Hiçbir başlangıç işe yaramazsa -1 döndür.

def strStr(haystack, needle):
    n, m = len(haystack), len(needle)
    for start in range(n - m + 1):
        j = 0
        while j < m and haystack[start + j] == needle[j]:
            j += 1
        if j == m:
            return start
    return -1

Knuth-Morris-Pratt

Sezgi

Kaba kuvvet yaklaşımının neleri gözden çıkardığına bakın. abcabcabd içinde abcabd ararken, 0. indeksteki deneme abcab ile eşleşir ve sonra başarısız olur. Bu beş harf ab ile biter ve ab aynı zamanda iğnenin başlangıcıdır. Dolayısıyla uyuşmazlıktan sonra, bir sonraki yararlı denemenin iki harfi zaten eşleşmiştir ve samanlıktaki aynı konumdan devam edebilirsiniz.

Bir dizenin sınırı, abcab içindeki ab gibi, aynı zamanda son ek de olan daha kısa bir ön ektir. Aramadan önce, lps tablosunu oluşturun; burada lps[i], needle[0..i] dizisinin en uzun sınırının uzunluğudur. abcabd için bu değer [0, 0, 0, 1, 2, 0] olur. Tablo yalnızca iğneye bağlıdır ve iğneyi kendisiyle eşleştiren aynı eşleştirme döngüsünü çalıştırarak oluşturulur.

Ardından samanlığı bir kez tarayın ve şimdiye kadar eşleşen iğne harflerinin sayısı olan k değerini tutun. Sıradaki harf needle[k] ile eşleşirse, k bir artar. Eşleşmezse, k değerini lps[k-1] olarak ayarlayın ve eşleşene veya k 0 olana kadar aynı harfi yeniden karşılaştırın. Bir sınıra geri dönmek hiçbir eşleşmeyi atlamaz: başarısız denemenin içinde başlayan her eşleşme, eşleşen kısmın bir sınırıyla başlamalıdır ve önce en uzun sınır denenir. k m değerine ulaştığında, eşleşme i-m+1 konumunda başlamıştır.

Doğrusal olmasının nedeni şudur: k, samanlıktaki her harf için en fazla bir artar ve her geri dönüş onu azaltır. Yükseldiğinden daha fazla kez düşemez; bu nedenle tarama en fazla 2n adım sürer ve tabloyu oluşturmak en fazla 2m adım alır.

Algoritma

lps dizisini oluştur: k = 0 ile başla; i için 1'den m-1'e kadar, k > 0 iken ve needle[i], needle[k]'den farklıyken k = lps[k-1] ile geri git; eşleşirlerse k'yi artır; lps[i] = k değerini kaydet.
k'yi 0'a sıfırla ve i indeksiyle haystack üzerinde ilerle.
k > 0 iken ve haystack[i], needle[k]'den farklıyken k = lps[k-1] değerini ata.
haystack[i], needle[k]'ye eşitse k'yi artır.
k, m'ye eşitse i-m+1 değerini döndür. Döngü biterse -1 döndür.

def strStr(haystack, needle):
    m = len(needle)
    # lps[i]: length of the longest proper prefix of needle[0..i] that is also its suffix
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and needle[i] != needle[k]:
            k = lps[k - 1]
        if needle[i] == needle[k]:
            k += 1
        lps[i] = k

    k = 0  # how many letters of needle are matched so far
    for i, ch in enumerate(haystack):
        while k > 0 and ch != needle[k]:
            k = lps[k - 1]  # fall back to the longest border, never move i back
        if ch == needle[k]:
            k += 1
        if k == m:
            return i - m + 1
    return -1

Tuzaklar ve uç durumlar

Hataların çoğu, saman yığınının sonunda veya geri dönüş döngüsünün içinde ortaya çıkar.

Başlangıcı n-m yerine n-1 değerine kadar ilerletmek. Saman yığınının sonu, iğnenin başlangıcıyla eşleştiğinde karşılaştırma haystack dizisinin sonunu aşar; bu da Python, Java, Rust ve Swift'te dizin hatasına yol açar.
İğnenin saman yığınından daha uzun olabileceğini unutmak. C++'taki size_t veya Rust'taki usize gibi işaretsiz uzunluklarda n-m negatif olamaz: C++ bunu çok büyük bir sayıya sarar, Rust ise hata ayıklama derlemesinde paniğe yol açar. Önce m > n koşulunu kontrol edin veya işaretli tamsayılarla hesaplama yapın.
KMP geri dönüşünü while yerine if olarak yazmak. aaa dizisini aabaa içinde ararken b için iki kez geri dönüş gerekir: 2'den 1'e, ardından 0'a. Tek geri dönüşten sonra durursanız b hiçbir şeyle eşleşmediği hâlde k 1'de kalır ve 2. dizinde var olmayan bir eşleşme bildirirsiniz.
KMP'de eşleşme olmadığında saman yığını dizinini geri almak. Yalnızca k değişir. i değerini geri almak, en kötü durumda O(n · m) karmaşıklığını geri getirir.
Eşleşmenin bittiği yeri veya 1 tabanlı bir dizini döndürmek. Yanıt, 0'dan sayılan başlangıç konumudur. Lua ve R dizeleri 1'den başlar, bu nedenle döndürmeden önce 1 çıkarın.
PHP'de en üst düzeyde strStr bildirmek. PHP işlev adlarında büyük-küçük harf ayrımı yapmadığından, bu ad yerleşik strstr işleviyle çakışır. PHP başlangıç kodu, bu nedenle işlevi kendi ad alanına yerleştirir.

Sıkça sorulan sorular4

Bir dizenin ilk geçtiği yeri bulmanın zaman karmaşıklığı nedir?

Her başlangıç konumunu kontrol etmek, en kötü durumda O(n · m) zaman alır; burada n ve m, haystack ve needle uzunluklarıdır ve O(1) ek alan kullanır. Knuth-Morris-Pratt algoritması, harfler ne olursa olsun O(n + m) zaman alır ve tablosu için O(m) alan kullanır.

KMP önek tablosu nasıl çalışır?

Needle'ın her ön eki için tablo, aynı zamanda sonek olan en uzun öz önekinin uzunluğunu saklar. k harf eşleştirildikten sonra bir uyuşmazlık olduğunda, bu k harf needle'ın bir ön ekidir ve lps[k-1] bunlardan kaçının bir sonraki olası eşleşmeyi başlatabileceğini belirtir. aabaaab için tablo [0, 1, 0, 1, 2, 2, 3] şeklindedir.

Neden yerleşik find veya indexOf yöntemini kullanmıyorsunuz?

Üretim kodunda bunu kullanmalısın; çünkü test edilmiştir ve hızlıdır. Görüşmeciler, doğru sınırlarla eşleşen döngüyü yazabildiğini görmek için bu problemi sorar ve genellikle devamında O(n · m) en kötü durumundan nasıl kaçınacağını sorarlar. Yerleşik bir aramanın en kötü durumu dile ve kütüphane sürümüne bağlıdır, bu yüzden bu soruya yanıt vermez.

Hashing kullanarak KMP yerine çözebilir misin?

Evet, Rabin-Karp algoritmasıyla. İğnenin hash’ini ve samanlıktaki m harflik her pencerenin kayan hash’ini hesaplayın; pencere kaydıkça bunu sabit zamanda güncelleyin. Harfleri tek tek yalnızca hash’ler eşleştiğinde karşılaştırın. Bu, beklenen O(n + m) zamanda çalışır, ancak çok sayıda hash çakışması süreyi yeniden O(n · m) değerine yaklaştırabilir.

Python

def strStr(haystack, needle):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

haystack = "bananarama"
needle = "ana"

Beklenen