Leksikoqrafiya (Həll təhlili)

Problemdə verilmiş n \cdot l hərfləri $n$ sözlərə, hər bir söz $l$ uzunluğunda olmaqla, leksikoqrafik sıralanmış şəkildə paylamaq lazımdır ki, $k$-cı söz mümkün olan ən kiçik leksikoqrafik söz olsun.

Leksikoqrafik sıralanma sözlərin simvollara görə soldan sağa sıralanması ilə müəyyən edilir. Buna görə də, $k$-cı sözü minimallaşdırmaq üçün, sözü mümkün qədər tez (ilk pozisiyalarda) mümkün olan ən kiçik hərflərlə doldurmaq lazımdır, bütün sözlərin sıralanmasını pozmadan.

Bu, aşağıdakı qreedy (acgöz) alqoritmə gətirib çıxarır:

1. Giriş hərflərini artan qaydada sıralayırıq.

2. İkiölçülü simvol matrisini qururuq

   v[1 .. n][1 .. l],

   burada hər bir sıra ayrıca bir sözdür.

3. Matrisi soldan sağa sütunlara görə doldururuq, çünki sütunlar sözlərdəki pozisiyalara uyğun gəlir və leksikoqrafik sıralanmaya təsir edir.

Birinci sütunun doldurulması

1. İlk sütuna yalnız $1$-dən $k$-ya qədər sıra nömrələri olan sözlərə hərflər veririk, istifadə edərək $k$ mümkün olan ən kiçik hərfi.

2. Bu hərflər üst-üstə, leksikoqrafik sıralamanı təsdiqləmək üçün aşağıdan yuxarıya yerləşdirilir.

3. k + 1, ..., n sıra nömrələri olan sözlər bu mərhələdə doldurulmur, çünki onlar $k$-cı sözün kiçikliyinə təsir etmir.

Beləliklə, biz $k$-cı sözün birinci simvolunun minimal olduğunu təmin edirik.

Sonrakı sütunların doldurulması

2, 3, ..., l sütunları üçün:

1. Sıra 1, ..., k arasında olan ən kiçik indeks $pt$ tapırıq ki, $pt$ və $k$ üçün sıralar əvvəlki sütunlarda 1, ..., j - 1 eynidir.

2. Bu sözlər silsiləsini [pt, k] - mövcud prefiksi üzrə $k$-dan fərqlənməyən bütün sözlərdir və buna görə də ondan böyük ola bilməz.

3. Sütun $j$ üçün əlçatan olan ən kiçik hərfləri yalnız $pt$-dən $k$-ya qədər sıra nömrələri ilə sözlərə veririk.

4. Proses $k$-cı söz üçün bütün $l$ simvol hansısa formada tamamlanana qədər təkrar edilir.

Qalan hüceyrələrin doldurulması

$k$-cı söz tam formalaşdıqdan sonra:

• Bütün qalan hərflər leksikoqrafik sıralanmanı pozmadan istənilən şəkildə paylana bilər.

• Məsələn, qalan hərfləri sıralanmış qaydada yuxarıdan aşağıya, soldan sağa sözlər üzrə müvafiq matrisi dolduraraq bir-bir paylamaq olar.

Düzgünlük

• Hər sütunda $k$-cı sözün cari simvolunu minimallaşdırırıq.

• Eyni və ya artan hərfləri prefiksi üzrə eyni olan bütün sözlərə veririk, beləliklə, sözlərin sıralamasını pozmuruq.

• $k$-cı söz tamamlandıqdan sonra atılan addımlar onu daha böyük edə bilməz.

Nəticədə, əldə edilmiş $k$-cı söz leksikoqrafik ən kiçikdir.

Misal

Bu testə baxın:

6 3 6
fgahhfgaaebdcbbebc

Burada $6$ söz, $3$ uzunluğunda olan sözlər formalaşdırmaq lazımdır, bütün hərflər istifadə olunaraq altıncı söz leksikoqrafik sıralanma siyahısında ən kiçik olsun.

Giriş sözünü sıralayırıq:

Ümumilikdə 18 = 6 \cdot 3 hərf, bu boyda matrisini 6 × 3 ölçüsündə göstərir.

Sütun 1. Sütunu birincidən altıncaya qədər olan sıraya yuxarıdan aşağıya hərflərlə doldururuq, çünki bu səbəbimizi maraqlandırır.

Sütun 2. İndi altıncı sıranın prefiksinə uyğun olan sözlərə baxırıq. Altıncı sıranın prefiksi birinci sütundan sonra "$b$" olur. Uyğun olan sözlər $4,5$ və $6$ sıradır. pt = 4 olan uyğun olan ən kiçik sıra nömrəsini tapırıq.

İkinci sütunda $4$-dən $6$-ya qədər olan sıra nömrələri ilə sözlərə mümkün olan ən kiçik hərfləri verir.

Sütun 3. Təkrarlanmış sütunun iki sütununu doldurulmuş "$bc$" prefiksinə uyğun olan sözləri axtarırıq. Uyğun sözlər $5$ və $6$ sıradır. pt = 5 olan uyğun olan ən kiçik sıra nömrəsini tapırıq. $5$-dən $6$-ya qədər olan sıra nömrələri ilə sözlər üçün mümkün olan ən kiçik hərfləri verir. İndi altıncı söz tam formalaşıb və "$bcd$" olur.

Qalan hərflərin doldurulması

Altıncı söz tam formalaşdıqdan sonra qalan hərfləri düzgün şəkildə istənilən formada yerləşdirə bilərik. Məsələn, qalan hərfləri leksikoqrafik sırayla yuxarıdan aşağıya və soldan sağa doğru sıralanmış şəkli ilə matrisi doldururuq.

Birinci testə baxın:

3 2 2
abcdef

Giriş sözündəki hərfləri sıralayın:

Biz $3$ söz üçün $2$ hərflə matrisi doldurmaqla leksikoqrafik minimallaşmanı təmin etmək üçün $2$-ci sözü minimallaşdırmalıyıq.

Əvvəlcə yalnız $1$-dən $2$-ci sıraya qədər olan sözlərlə yuxarıdan aşağıya hərfləri dolduraraq ilk sütunu. Bu sözlərdən minimal olan sözlərin təsiri altındadır.

Daha sonra ikinci sütuna keçir. İkinci sütun özündəki ilk prefiksi $2$-ci sırayla uyğun gələn ən erkən sıradan başlayaraq doldurmalı. Bu durumda həmin sıra $2$-ci sıra olur, buna görə pt = 2. İkinci sütunu olan sözlər arasında $pt$ sıra nömrəsindən başlayaraq $2$ sıra nömrəsinə qədər hərf doldurur.

Sonra qalan hərfləri leksikoqrafik sırayla yuxarıdan aşağıya və soldan sağa doğru dağıtarıq. Bu düzgün cavabın formalaşmasını tamamlayır.

Alqoritmin implementasiyası

Giriş məlumatlarını oxuyun.

cin >> n >> l >> k;
cin >> s;

Girişdəki sözlərin hərflərini sıralayın. Hal-hazırda işlənən hərf $s[pos]$ olacaq.

pos = 0;
sort(s.begin(), s.end());

$n$ söz üçün $l$ sütun olan nəticə matrisini $v$ elan edək, hər bir söz uzunluq $l$ olan bir sıraya uyğun gəlir.

vector<string> v(n, string(l, ' '));

$pt$-dan $k$-1-ə qədər olan sıra nömrələri ilə $j$ sütununda hərfləri paylamaq üçün hazırlanırıq (sıra nömrələri sıfırdan başlanır).

int pt = 0;
for (j = 0; j < l; j++)
{
  for (i = pt; i < k; i++)
    v[i][j] = s[pos++];

$pt$ göstəricisini irəli sürmək (pt++) üçün $j$-cü simvol (k - 1)-ci sıranın $j$-cü simvoluna bərabər olana qədər davam edirik. Nəticə olaraq, $pt$ göstəricisi k - 1 sıra prefiksinə uyğun olan ən kiçik sıra nömrəli sıraya göstərəcək.

  while (v[pt][j] != v[k - 1][j]) pt++;
}

Bundan sonra matrisin qalan hüceyrələrini doldururuq. Bunun üçün sırayla sözlərin üstünə sürətlə yuxarıdan aşağıya və soldan sağa keçərək qalan hərfləri paylayır.

for (i = 0; i < n; i++)
for (j = 0; j < l; j++)
  if (v[i][j] == ' ') v[i][j] = s[pos++];

Cavabı çıxarın.

for (i = 0; i < n; i++)
  cout << v[i] << endl;