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

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

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>