Secvențe de tip n-ouroboros

Descrierea algoritmului

Fie L lungimea șirului s. Prefixul de lungime n ocupă pozițiile 0, 1, …, n − 1, iar sufixul de lungime n ocupă pozițiile L − n, …, L − 1. Cele două secvențe nu se suprapun dacă n − 1 < L − n, adică 2n ≤ L. Valorile posibile ale lui n sunt deci 1, 2, …, [L / 2].

În subprogramul ouroboros, n ia valorile de la [L / 2] până la 1, în ordine descrescătoare. Pentru fiecare valoare se compară primele n caractere ale lui s cu ultimele n caractere, folosind funcția strncmp, apelată pentru adresa s și pentru adresa s + L − n. Prima valoare pentru care secvențele sunt egale este cea maximă și se returnează imediat. Dacă nicio valoare nu convine, subprogramul returnează 0.

În programul principal, textul se citește cu cin.getline și se împarte în cuvinte cu funcția strtok, având ca separator spațiul. Fiecare cuvânt se memorează, în forma din text, într-un tablou de cuvinte. Subprogramul primește numai litere mici, deci pentru fiecare cuvânt se face o copie în care literele mari sunt transformate în litere mici. Subprogramul se apelează pentru această copie, iar valoarea returnată se memorează în tabloul val și se compară cu maximul determinat până atunci.

După prelucrarea tuturor cuvintelor, dacă maximul a rămas 0, se afișează NU. Altfel se afișează maximul, iar pe linia următoare cuvintele pentru care valoarea memorată este egală cu maximul, în ordinea din text.

Programul

#include <iostream>
#include <cstring>
using namespace std;

char text[101], cuv[51][101];
int val[51];

/* Intoarce cea mai mare valoare n pentru care primele n litere ale lui s
   coincid cu ultimele n, iar cele doua secvente nu se suprapun (2n <= L). */
int ouroboros(char s[]) {
    int L = strlen(s);
    for (int n = L / 2; n >= 1; n--)
        if (strncmp(s, s + L - n, n) == 0)
            return n;
    return 0;
}

int main() {
    char mic[101];
    int k = 0, maxim = 0;

    cin.getline(text, 101);

    char *p = strtok(text, " ");
    while (p != NULL) {
        k++;
        strcpy(cuv[k], p);

        /* copia cuvantului, cu literele mari transformate in litere mici */
        strcpy(mic, p);
        for (int i = 0; mic[i] != '\0'; i++)
            if (mic[i] >= 'A' && mic[i] <= 'Z')
                mic[i] = mic[i] + ('a' - 'A');

        val[k] = ouroboros(mic);
        if (val[k] > maxim)
            maxim = val[k];

        p = strtok(NULL, " ");
    }

    if (maxim == 0)
        cout << "NU";
    else {
        cout << maxim << "\n";
        int primul = 1;
        for (int i = 1; i <= k; i++)
            if (val[i] == maxim) {
                if (primul == 0)
                    cout << " ";
                cout << cuv[i];
                primul = 0;
            }
    }

    return 0;
}