O (n) 'de bir dizede farklı alt dizelerin sayısını saymak mümkün mü?

Question

n uzunluğunda bir dizi verildiğinde, s içinde O (n) 'de farklı alt dizelerin sayısını saymak mümkün mü?

Örnek

Girdi: abb

Çıktı: 5 ('abb', 'ab', 'bb', 'a', 'b')

biraz araştırma yaptım ama böyle bir in bu sorunu çözer bir algoritma bulmak gibi olamaz verimli yol Bir O (n^2) yaklaşımın mümkün olduğunu biliyorum, ancak daha verimli bir algoritma var mı?

Her bir alt dizgiyi, yalnızca farklı olanların (fark yaratması durumunda) toplam sayısını almam gerekmez.

Answer 1

Sen doğrusal zamanda bir sonek ağacı inşa etmek Ukkonen algoritmasını kullanarak Doğrusal zamanda. Tüm düğümlerdeki toplam karakter sayısıdır. Ağaçta

  /\     
      b a 
      | b 
      b b 

5 karakterden yüzden 5 altdizgelerin:

Örneğin, örnek gibi bir sonek ağacı üretir. Her benzersiz dize, farklı bir harfin ardından kök bitişinden bir yoldur: abb, ab, a, bb, b. Yani dizelerin sayısı ağaçtaki harflerin sayısıdır. Daha doğrusu

:

• Her alt dize dize bazı sonekin öneki;
• Tüm son ekler trie'dedir;
• Bu yüzden, trie boyunca alt diziler ve yollar arasında 1-1 yazışma var (trie tanımıyla);
  • her biri farklı boş olmayan yol onun son harfi sonra ayrı bir pozisyonda biter; çünkü: ve
  • ağaç ve boş olmayan yollarında harfler arasında bir 1-1 yazışma vardır ve
  • her harfin aşağıdaki pozisyona yolu, O O (N^2) karakterler içeren bir ağaç inşa etmenin mümkün olabileceğini merak kişiler için

NOT benzersizdir (N) süre:

Sonek ağacının gösterimi için bir numara var. Ağacın düğümlerindeki gerçek dizeleri depolamak yerine, işaretçileri orignal dizgede saklarsınız, böylece "abb" içeren düğüm "abb" ye sahip değildir, (0,3) - 2 tamsayıya sahiptir. düğüm, her düğümdeki dizenin uzunluğu ne olursa olsun ve sonek ağacında O (N) düğümleri bulunur.

Answer 2

LCP array dosyasını oluşturun ve toplamını alt dizelerden (n (n + 1)/2) alın.

https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm

s alt dizeleri sayısı sadece hesaplayabilir trie, dizeleri önekleri sayısı o zaman: