Bazı koşulların yerine getirilmesiyle ilgili minimum bir dizgenin aranması

Question

Geçtiğimiz günlerde, bir röportaj sırasında aşağıdaki soruyu sordum. Bir dize S verildiğinde, S2'nin S'nin bir alt dizisi olduğu ve ayrıca S'nin S2 + tersinin (S2) bir alt dizisi olduğu bir S2 dizisini bulmam gerekiyor. Burada '+', birleştirme anlamına gelir. Verilen S2 için mümkün olan en düşük S2 uzunluğunu vermem gerekiyor. Bunun bir dinamik programlama problemi olduğu ancak çözemediğim söylendi. Birisi bana bu problemde yardımcı olabilir mi?

Edit

O (N) ya da daha az, bu yapmak için bir yol var.

Answer 1

S'den her karakter S2'ye dahil olabilir veya eklenemez. Bunun üzerine iki vaka çalışır özyinelemeye hazırlayabilirsiniz:

S
• ilk karakteri kapak için kullanılan değil S'nin
• ilk karakteri kapak için kullanılır ,

ve minimum hesaplamak Bu iki kapak. Bunu uygulamak için S'nin ne kadarının S2 + tersine (S2) seçildiğini izlemek yeterlidir.

Hangi sonucun bulunduğunu (kapak, kapak bulunamaz) bildiğimiz yerde optimizasyonlar vardır ve bir şey içermeyecekse, kapak için ilk karakteri almak gerekli değildir.

Basit piton uygulaması:

cache = {} 

def S2(S, to_cover): 
    if not to_cover: # Covered 
     return '' 
    if not S:   # Not covered 
     return None 
    if len(to_cover) > 2*len(S): # Can't cover 
     return None 
    key = (S, to_cover) 
    if key not in cache: 
     without_char = S2(S[1:], to_cover)  # Calculate with first character skipped 
     cache[key] = without_char 
     _f = to_cover[0] == S[0] 
     _l = to_cover[-1] == S[0] 
     if _f or _l: 
      # Calculate with first character used 
      with_char = S2(S[1:], to_cover[int(_f):len(to_cover)-int(_l)]) 
      if with_char is not None: 
       with_char = S[0] + with_char # Append char to result 
       if without_char is None or len(with_char) <= len(without_char): 
        cache[key] = with_char 
    return cache[key] 

s = '21211233123123213213131212122111312113221122132121221212321212112121321212121132' 
c = S2(s, s) 
print len(s), s 
print len(c), c 

Answer 2

en S2 "elma" olduğunu varsayalım.

S2 + reverseS2> = S> = S2
"appleelppa"> = S> = "elma"

Yani: O zaman bu varsayımı yapabilirsiniz Verilen S "elma" dahil olmak üzere "elma" den fazla bir şey olmaz. "Elma" veya "elma" olabilir.

String S ="locomotiffitomoc"; 
// as you see S2 string is "locomotif" but 
// we don't know S2 yet, so it's blank 
String S2 = ""; 
for (int a=0; a<S.length(); a++) { 
    try { 
     int b = 0; 
     while (S.charAt(a - b) == S.charAt(a + b + 1)) 
      b++; 
     // if this for loop breaks that means that there is a character that doesn't match the rule 
     // if for loop doesn't break but throws an exception we found it. 
    } catch (Exception e) { 
     // if StringOutOfBoundsException is thrown this means end of the string. 
     // you can check this manually of course. 
     S2 = S.substring(0,a+1); 
     break; 
    } 
} 
System.out.println(S2); // will print out "locomotif" 

Tebrikler, en düşük S2'yi buldunuz.

Answer 3

Bu sorunun iki önemli yönü vardır. Biz S2 + geri (S2) bir alt dizge S gerektiğinden

1. S2 en az n/2 uzunluğuna sahip olmalıdır. S2 Birleştirme sonrasında
2. ve geri (S2) alfabe nedenle çözelti, S son S merkezinden kontrol etmektir gibi

tekrar eden bir model vardır herhangi bir ardışık eleman için.Birini bulursanız, gösterildiği gibi her iki taraftaki öğeleri kontrol edin. Şimdi

Eğer dizesinin sonuna kadar ulaşması mümkün ise, o zaman elementlerin (sonuç) minimum sayısı ardışık elemanlarını bulmak noktaya baştan mesafedir. Bu örnekte, bunun Cı.ı 3

Bunun her zaman olmayabileceğini biliyoruz. Yani merkezde ardışık elemanlar bulamayabilirsiniz. Ardışık elemanların merkezden sonra olduğunu söyleyelim, o zaman aynı testi yapabiliriz.

Ana dize

Alt dize

Kısaltılmış dize

Şimdi t geldiğinde O büyük şüphe. Neden merkezden başlayarak sadece sol tarafı düşünüyoruz? Cevap basittir, birleştirilmiş dizgi S + reverse (S) ile yapılır. Bu yüzden, dizideki son öğenin, birleştirilmiş dizede ardışık olarak geldiğinden eminsin. vermek ardışık alfabeler aranıyor : en azından nihai birleştirilmiş Şimdi dize

karmaşıklık meselesi n alfabe olmalıdır çünkü ana dize ilk yarısında herhangi tekrarı daha iyi bir sonuç verebilir hiçbir yolu yoktur Maksimum O (n) Şimdi her iki taraftaki elemanları iteratif olarak kontrol etmek, O (n) 'nin en kötü durum karmaşıklığını verebilir. yani maksimum n/2 karşılaştırmaları. İkinci kontrolün yapılmasında birçok kez başarısız olabiliriz, böylece karmaşıklıklar yani O (n * n) arasında bir çoğullayıcı ilişkiye sahibiz.

Bunun doğru bir çözüm olduğuna inanıyorum ve henüz bir boşluk bulamadık.