View source for 3398 - Kps

Un cuvânt se numește '''k'''-ps dacă prefixul său de lungime '''k''' este identic cu sufixul de lungime '''k''', iar '''k''' este cea mai mare valoare strict mai mică decât lungimea cuvântului, cu această proprietate. Dacă nu există nicio astfel de valoare '''k''' nenulă, spunem despre cuvânt că este '''0'''-ps. De exemplu, '''amalgam''' este '''2'''-ps, iar '''amestec''' este '''0'''-ps.

== Cerinţa ==
Rezolvați următoarele cerințe:

1) Se dă un cuvânt. Determinați '''k''' asfel încât cuvântul să fie '''k'''-ps.

2) Se dă un șir de caractere în care cuvintele sunt alcătuite din litere mici ale alfabetului englez și sunt separate prin spații. Să se afișeze în ordine cuvintele '''0'''-ps, '''1'''-ps, '''2'''-ps, '''3'''-ps, etc, până la cel mai mare '''k''' pentru care există în șir cel puțin un cuvânt '''k'''-ps. Pentru fiecare categorie, cuvintele vor fi afișate în ordine alfabetică.
== Date de intrare ==
 Fișierul de intrare '''kpsin.txt''' conține pe prima linie numărul '''C''', care reprezintă cerința și poate fi '''1''' sau '''2'''.

* Dacă '''C=1''', a doua linie conține un cuvânt format litere mici ale alfabetului englez.
* daca '''C=2''', a doua linie conține șir de caractere în care cuvintele sunt alcătuite din litere mici ale alfabetului englez și sunt separate prin spații.
== Date de ieșire ==
* Dacă '''C=1''', fișierul de ieșire '''kpsout.txt''' va conține pe prima linie numărul '''K''', astel încât cuvântul dat este cuvânt '''K'''-ps. Dacă cuvântul dat nu este cuvânt '''k'''-ps, se va afișa valoarea '''0'''.
* Dacă '''C=2''', fișierul de ieșire '''kpsout.txt''' va conține mai multe linii:
* prima linie corespunde cuvintelor '''0'''-ps, a doua corespunde cuvintelor '''1'''-ps, a treia cuvintelor '''2'''-ps, etc.
* fiecare linie începe cu numărul de cuvinte din categoria curentă, urmat de un spațiu și de aceste cuvinte, in ordine alfabetică, separate prin câte un spațiu;
* dacă nu există niciun cuvânt dintr-o anumită categorie, linia corespunzătoare va conține doar valoarea '''0'''.

== Restricţii şi precizări ==
* pentru '''C=1''', cuvântul dat va avea cel mult '''1000''' de litere;
* pentru '''C=2''', șirul dat va avea cel mult '''10000''' de caractere, fiecare cuvânt având cel mult '''100''' de litere;
* pentru 50 de puncte, '''C=1'''.
== Exemplu 1 ==
; kpsin.txt
 1
 amalgam
; kpsout.txt
 Datele de intrare corespund restrictiilor impuse
 2
<br>
== Exemplu 2 ==
; kpsin.txt
 2
 asdfqwasdf zar amalgam  zarzar  barbar ghjtttyuttghj asaswasas kps
; kpsout.txt
 Datele de intrare corespund restrictiilor impuse
 2 kps zar
 0
 1 amalgam
 3 barbar ghjtttyuttghj zarzar
 2 asaswasas asdfqwasdf
== Exemplu 3 ==
; kpsin.txt
 1
 ASD SCCS
; kpsout.txt
 Datele de intrare nu corespund restrictiilor impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
def k_ps(cuvant):
    # Determină k pentru care cuvântul este k-ps
    for k in range(len(cuvant) - 1, 0, -1):
        if cuvant[:k] == cuvant[-k:]:
            return k
    return 0


def sortare_cuvinte(sir):
    # Sortează cuvintele în funcție de valoarea k
    cuvinte = sir.split()
    k_cuvinte = {k: [] for k in range(max(map(k_ps, cuvinte)) + 1)}
    for cuvant in cuvinte:
        k_cuvinte[k_ps(cuvant)].append(cuvant)
    for k in k_cuvinte:
        k_cuvinte[k].sort()
    return k_cuvinte


def main():
    with open('kpsin.txt', 'r') as fin, open('kpsout.txt', 'w') as fout:
        c = int(fin.readline().strip())

        # Verifică dacă datele de intrare respectă restricțiile
        if c == 1:
            cuvant = fin.readline().strip()
            if len(cuvant) > 1000 or not cuvant.islower():
                fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
                return
            fout.write("Datele de intrare corespund restrictiilor impuse\n")
            fout.write(str(k_ps(cuvant)) + '\n')
        elif c == 2:
            sir = fin.readline().strip()
            if len(sir) > 10000 or not all(cuvant.islower() for cuvant in sir.split()):
                fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
                return
            fout.write("Datele de intrare corespund restrictiilor impuse\n")
            k_cuvinte = sortare_cuvinte(sir)
            for k in k_cuvinte:
                fout.write(str(len(k_cuvinte[k])) + ' ' + ' '.join(k_cuvinte[k]) + '\n')


if __name__ == "__main__":
    main()


</syntaxhighlight>