# PBinfo #3398 – kps – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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 kps.in 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 kps.out 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 kps.out 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.

Exemplul 1
kps.in

1
amalgam
kps.out

2
Exemplul 2
kps.in

2
asdfqwasdf zar amalgam  zarzar  barbar ghjtttyuttghj asaswasas kps
kps.out

2 kps zar
0
1 amalgam
3 barbar ghjtttyuttghj zarzar
2 asaswasas asdfqwasdf

## Cod sursă C++

```cpp
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("kps.in");
ofstream fout("kps.out");
int C;
char S[10001], * V[10001];
int K[10001], n;
int kps(char * S)
{
    int R = 0;
    for(int i = strlen(S) - 1 ; i > 0 ; i --)
        if(strstr(S , S + i) == S)
            R = strlen(S) - i;
    return R;
}
int main(){
    fin >> C;
    fin.get();
    fin.get(S, sizeof(S));
    if(C == 1)
    {
        fout << kps(S) << endl;
    }
    else
    {
        char * p = strtok(S , " ");
        while(p)
            V[++n] = p, p = strtok(NULL, " ");
        sort(V + 1 , V + n + 1, [](char * A , char * B){
            return strcmp(A , B) < 0;
        });
        int M = 0;
        for(int i = 1 ; i <= n ; i ++)
        {
            K[i] = kps(V[i]);
            M = max(M , K[i]);
        }
        for(int j =  0 ; j <= M ; j ++)
        {
            int cnt = 0;
            for(int i = 1 ; i <= n ; i ++)
                if(K[i] == j)
                    cnt ++;
            fout << cnt << " ";
            for(int i = 1 ; i <= n ; i ++)
                if(K[i] == j)
                    fout << V[i] << " ";
            fout << "\n";
        }
    }
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3398)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3398/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3398/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)