Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 32

## [31-35 soruları için açıklama]
Verilen bir **S** karakter dizisinin içinde daha küçük bir **P** dizisinin karakterleri sırayla fakat ardışık olma şartı olmadan geçiyorsa bu durumu **gizli alt-dizi** olarak adlandırmaktayız. Mesela aşağıdaki **S** dizisinde
### gmtcoarbbhpoheaccvbttya
12345678901234567890123
**merhaba** dizisi [2,4,7,10,15,19,23] indislerinde gizli alt-dizi olarak geçmektedir. Aynı **merhaba** dizisi ayrıca [2,4,7,13,15,19,23] indislerinde de gizli alt-dizi olarak geçmektedir. Verilen bir **P** dizisinin bir **S** dizisi içinde kaç kez gizli alt-dizi olarak geçtiğini aşağıdaki özyineli yöntem ile bulabiliriz. **F(i,j)** fonksiyonu **P** dizisinin ilk **i** karakterinin **S** dizisinin ilk **j** karakteri içinde kaç kez gizli alt-dizi olarak geçtiğini göstersin. |**P**| de bir dizideki karakter sayısını ve **P[i]** **P** dizisinin **i**. karakterini göstersin.
\[F(0,0) = 1\]
\[F(i,0) = 0 \quad 1'den |P|'ye kadar olan i değerleri için\]
\[F(0,j) = 1 \quad 1'den |S|'ye kadar olan j değerleri için\]
\[F(i,j) = F(i,j-1) \text{ eğer } P[i] S[j]'den farklı ise\]
\[F(i,j) = F(i-1,j-1) + F(i,j-1) \text{ eğer } P[i] \text{ ve } S[j] \text{ aynı karakter ise}\]
Bir **P** dizisinin bir **S** dizisi içinde kaç kez gizl i alt-dizi olarak geçtiğini bulmak için **F(|P|,|S|)** değerini hesaplamak yeterli olacaktır.
Sadece ‘A’ karakterlerinden oluşan **M** uzunluğundaki bir dizide sadece ‘A’ karakterlerinden oluşan **N** uzunluğundaki bir dizi kaç kez gizli alt-dizi olarak geçer?
A) **M**!
B) **N**!
C) **M**! / **N**!
D) **M**! / ((**M**-**N**)!-**N**!)
E) **M**!-**N**!
Aynı karakterlerden oluşan iki dizi verildiğinde küçük dizinin büyük dizi içerisinde kaç kez gizli alt-dizi olarak bulunduğu sorusu “M adet karakter içinde kaç farklı şekilde N adet karakter seçebiliriz?” sorusu ile aynı soru haline gelir. Bu da **M**’nin **N**’li kombinasyonuna eşittir yani cevap D şıkkıdır.

---

‘ABABABAB’ dizisinde ‘ABA’ dizisi kaç kez gizli alt-dizi olarak geçer?

Şıklar:
A) 3 | B) 6 | C) 8 | D) 10 | E) 20

Cevap: E 20

Çözüm:
Açıklamalarda verilen özyineli fonksiyonu kullanıp 4x9 boyutundaki aşağıdaki matrisi doldurduğumuzda cevabın matrisin sağ alt köşesinde bulunan 10 olduğunu görürüz.
<table><tr><td></td><td>-</td><td>A</td><td>B</td><td>A</td><td>B</td><td>A</td><td>B</td><td>A</td><td>B</td></tr><tr><td>-</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>A</td><td>0</td><td>1</td><td>1</td><td>2</td><td>2</td><td>3</td><td>3</td><td>4</td><td>4</td></tr><tr><td>B</td><td>0</td><td>0</td><td>1</td><td>1</td><td>3</td><td>3</td><td>6</td><td>6</td><td>10</td></tr><tr><td>A</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>4</td><td>4</td><td>10</td><td>10</td></tr></table>
Açıklamalarda verilen özyineli fonksiyonu kullanıp 4x13 boyutundaki aşağıdaki matrisi doldurduğumuzda cevabın matrisin sağ alt köşesinde bulunan 12 olduğunu görürüz.
<table><tr><td></td><td>-</td><td>A</td><td>B</td><td>C</td><td>C</td><td>B</td><td>A</td><td>A</td><td>B</td><td>C</td><td>C</td><td>B</td><td>A</td></tr><tr><td>-</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>A</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td><td>3</td><td>3</td><td>3</td><td>3</td><td>3</td><td>4</td></tr><tr><td>B</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>2</td><td>2</td><td>5</td><td>5</td><td>5</td><td>8</td><td>8</td></tr><tr><td>C</td><td>0</td><td>0</td><td>0</td><td>1</td><td>2</td><td>2</td><td>2</td><td>2</td><td>7</td><td>12</td><td>12</td><td>12</td></tr></table>