İzomorf suffiks ağacları

Bu tapşırıqda, verilmiş kök ağacına T izomorf olan '0' və '1' simvollarından ibarət müxtəlif sətirlərin sayını tapmaq lazımdır.

İki kök ağacı izomorf adlanır, əgər hər ikisi eyni sayda n zirvədən ibarətdirsə və hər birinin zirvələrini 1-dən n-ə qədər müxtəlif tam ədədlərlə nömrələmək mümkündürsə ki:

• hər iki ağacın kökləri eyni nömrələrə malikdir;

• birinci ağacda a və b nömrəli zirvələr arasında kənar varsa, yalnız o halda ikinci ağacda da a və b nömrəli zirvələr arasında kənar var.

Bu tapşırıqda sətir s üçün sufix ağacı aşağıdakı şərtlərə cavab verən kök ağacıdır:

1. Ağacın hər bir kənarına '0' və '1' simvollarından ibarət boş olmayan bir sətir uyğun gəlir.

2. Sətirin s+''} hər bir sufixinə, sufix "\textbf{" istisna olmaqla, yalnız bir yarpaq (yəni köklə üst-üstə düşməyən dərəcəsi 1 olan zirvə) uyğun gəlir ki, kökdən bu yarpağa qədər olan yolda kənarların sətirlərinin konkatenasiyası həmin sufixə bərabərdir.

3. Ağacın nə yarpaq, nə də kök olmayan hər hansı bir zirvəsinin dərəcəsi ikidən çoxdur.

4. Ağac, 1-3 xüsusiyyətlərinə cavab verən bütün ağaclar arasında kənarlarda yazılmış sətirlərin ümumi uzunluğu mümkün olan ən minimal olanıdır.

Məsələn, "1100" sətiri üçün sufix ağacı aşağıdakı kimidir:

Xatırladaq ki, sizin tapşırığınız verilmiş kök ağacına T görə, sufix ağacları T-yə izomorf olan '0' və '1' simvollarından ibarət müxtəlif sətirlərin sayını müəyyən etməkdir.