Bir dize içinde bir subsequence yinelenme bul

Örneğin, dize pi sayısının ilk 10 hanesi olsun, 3141592653 ve subsequence 123. Sırası iki kez oluşur:

3141592653
 1    2  3
   1  2  3

Bu soruya cevap veremedim ve verimli bir algoritma bulamıyorum ve bu durum beni rahatsız ediyor bu röportaj bir soru oldu. Basit bir düzenli ifade ile yapmak mümkün olmalı hissediyorum, ama 1.*2.*3 gibi olanlar her subsequence dönüş yok. Python saf benim uygulama (her 1 sonra 3 Her 2 sayısı) bir saat koşu oldu ve bitti.

CEVAP

29 Temmuz 2011, Cuma

Bu dynamic programming klasik bir sorun (ve genellikle düzenli ifadeler kullanarak çözülmüş değil).

Saf benim uygulama (her 1 sonra 3 Her 2 sayısı) bir saat koşu oldu ve bitti.

Buna üstel zamanda çalışan kapsamlı arama bir yaklaşım olurdu. (Saat olsa çalışır şaşırdım).

İşte dinamik programlama çözümü için bir öneri:

Özyinelemeli bir çözüm için film

(Uzun açıklama için, ama her adım çok basittir özür sabret ;-)

Eğersubsequencebir eşleşme bulunursa boş (basamak maç kaldı!) ve 1 dönüyoruz
Eğergiriş sırasıbizim basamak tükenmiş ettik boş ve muhtemelen bir eşleşme yok 0 dönüyoruz böylece
(Ne sırası ne de subsequence boş.)
(Varsayalım "abcdef"giriş sırasını gösterir, ve"xyz" demektir subsequence.)
Set 6* *0
Sayısı için maçlar result Eklebcdefvexyz(yani, ilk giriş basamak ve recurse atmak)
Eğer ilk iki hanesi aynı, yanibir=x
- Sayısı için maçlar result Eklebcdefveyz(yani, kalan subsequence basamak ilk basamak subsequence ve recurse maç)
result dönüş

Örnek

İşte özyinelemeli bir örnek giriş için çağırır 1221 /12. (Kalın yazı tipi, * * Subsequence; boş bir dize temsil eder.)

enter image description here

Dinamik programlama

Eğer saf bir şekilde uygulandığı takdirde, (alt)bazı sorunlar birden çok kez çözüldü (&; / 2 örneğin yukarıdaki şekilde*). Dinamik programlama, daha önce çözülmüş subproblems (genellikle bir arama tablosu) sonuçları hatırlayarak böyle gereksiz hesaplamaları önler.

Bu durumda olan bir masa ayarladık

[sıra 1 uzunluk] satır, ve
[subsequence 1 uzunluk] sütun:

enter image description here

Fikri 221 / eşleşme sayısını doldurmak gerekir2ilgili satır / sütun. Bir kere yapılır, hücre içinde nihai çözüm 1221 / yapmalıyız12.

Tablo doldurma hemen biliyoruz ne ile başlar ("temel durumda"):

Hayır subsequence basamak kaldı, 1 tam maç var:

enter image description here

Hayır sıra basamak kaldı, maçlar: herhangi bir şeyimiz yok

Biz daha sonra yukarıdan aşağıya / soldan sağa aşağıdaki kurala göre tablo doldurma devam edin:

Hücrede [satır][col] değeri bulunan yazma [satır-1][col].

Sezgisel olarak bu demek"221 / için maç sayısı2içerir 21 / tüm maçlar2."
Eğer satır sırasısatırve sütunda subseqcolaynı rakam ile başlayamaz, değer katmak bulunan [satır-1][col-1] değeri sadece yazılısatır][col].

Sezgisel olarak bu demek"1221 / için maç sayısı12ayrıca 221 / için tüm maçları içerir12."

enter image description here

Sonuç aşağıdaki gibi görünüyor

enter image description here

ve sağ alt hücre değeri aslında 2.

Kod

Python, (özür dilerim).

class SubseqCounter {

    String seq, subseq;
    int[][] tbl;

    public SubseqCounter(String seq, String subseq) {
        this.seq = seq;
        this.subseq = subseq;
    }

    public int countMatches() {
        tbl = new int[seq.length()   1][subseq.length()   1];

        for (int row = 0; row < tbl.length; row  )
            for (int col = 0; col < tbl[row].length; col  )
                tbl[row][col] = countMatchesFor(row, col);

        return tbl[seq.length()][subseq.length()];
    }

    private int countMatchesFor(int seqDigitsLeft, int subseqDigitsLeft) {
        if (subseqDigitsLeft == 0)
            return 1;

        if (seqDigitsLeft == 0)
            return 0;

        char currSeqDigit = seq.charAt(seq.length()-seqDigitsLeft);
        char currSubseqDigit = subseq.charAt(subseq.length()-subseqDigitsLeft);

        int result = 0;

        if (currSeqDigit == currSubseqDigit)
            result  = tbl[seqDigitsLeft - 1][subseqDigitsLeft - 1];

        result  = tbl[seqDigitsLeft - 1][subseqDigitsLeft];

        return result;
    }
}

Karmaşıklığı

Bu "masaya doldurun" yaklaşım karmaşıklığı anlamaya önemsiz olmasıdır. bonus İş sabit bir miktar her hücre için yapılır, ve uzunluğu satır sırası ve uzunluğu subsequence sütunlar var. Karmaşıklığı verirO(MN)neredeMveNdizilerin uzunlukları göstermek.

Bunu Paylaş: