Konkatenasiya#2526

Konkatenasiya

1 saniyə

64 meqabayt

Asan

İki $α$ və $β$ sətirinə baxaq. Onların konkatenasiyası, $β$ sətirinin $α$ sətrinə ardıcıl əlavə edilməsi nəticəsində alınan sətirə deyilir. Bu sətir $α β$ kimi işarə olunur. Məsələn, ' $ab$ ' və ' $a c$ ' sətirlərinin konkatenasiyası ' $aba c$ ' sətridir. Aydın məsələdir ki, bu tərif istənilən sayda sətrin konkatenasiyasına təbii şəkildə yayılır. Beləliklə, sıfır sayda sətrin konkatenasiyası boş sətir olacaq, bir sətrin konkatenasiyası isə elə həmin sətrin özü olacaq.

Gəlin $W$ adlı sətirlərdən ibarət bir çoxluğa baxaq. Bu çoxluğun bağlanışı $W^{*}$ W^{*} adlanır və elə, yalnız o sətirlərdən ibarət olur ki, onları $W$ çoxluğundan sıfır və ya daha çox sətrin konkatenasiyası şəklində almaq olar. Beləliklə, $W^{*}$ W^{*} çoxluğuna boş sətir daxildir və əgər $α$ sətri $W^{*}$ W^{*}-yə, $β$ sətri isə $W$ -yə aiddirsə, onda $α β$ sətri də $W^{*}$ W^{*}-yə aiddir. Üstəlik, $W^{*}$ W^{*} çoxluğunun bütün elementlərini belə şəkildə yazmaq olar, yəni $W^{*}$ W^{*} yuxarıda sadalanan xassələrə malik bütün çoxluqların kəsişməsidir. Məsələn, əgər $W = {a, ab}$ W=\{a, ab\} olarsa, $W^{*}$ W^{*} çoxluğu, hər ' $b$ ' hərfindən əvvəl ən azı bir ' $a$ ' hərfi olan bütün sətirlərdən ibarət olacaq.

Verilmiş $W$ sətirlər çoxluğu üçün $X$ çoxluğunu tapmaq tələb olunur ki, $W^{*} = X^{*}$ W^{*}=X^{*} və $X$ çoxluğunun elementlərinin sayı mümkün qədər az olsun. Əgər belə çoxluqlar bir neçədırsə, istənilən biri uyğundur. Məsələn, $W = {a, aabb, ab, a c, b, ba c}$ W=\{a, aabb, ab, ac, b, bac\} olduqda, şərtləri ödəyən yeganə çoxluq ${a, a c, b}$ \{a, ac, b\} olacaq.

Giriş

Giriş faylı $W$ çoxluğunun sətirlərindən ibarətdir, hər sətr çoxluğun bir elementidir. $W$ çoxluğunun hər bir sətri girişdə ən azı bir dəfə verilib. Giriş faylında bütün sətirlərin ümumi uzunluğu $1 0^{4}$ 10^4-dən çox deyil. Fayldakı sətirlərin sayı $1 0^{4}$ 10^4-dən çox deyil. $W$ -dəki hər sətrin ardınca faylda sətirsonu simvolları gəlir (ASCII kodları $13$ və $10$ olan iki simvol). Sətirlər yalnız ASCII kodları $33$ -dən $126$ -dək olan simvollardan ibarətdir.

Çıxış

Çıxış faylında tapılan $X$ çoxluğunun elementlərini leksikoqrafik minimal ardıcıllıqla verin. $X$ çoxluğunun hər bir sətri çıxışda yalnız bir dəfə yazılmalıdır. Sətirlər (sözlərdə olduğu kimi) leksikoqrafik sırada olmalıdır (bu sırada ' $ab$ ' sətri ' $aba$ ' sətrindən, ' $ab$ ' sətri isə ' $a c$ ' sətrindən kiçik sayılır).

Nümunələr

Nümunə 1