Problema Siruri Periodice

Un sir de caractere se spune ca are perioada k daca poate fi format din concatenarea unuia sau mai multor siruri de lungime k. De exemplu sirul „abcabcabcabc” are perioada 3, deoarece poate fi considerat ca 4 repetitii ale sirului „abc”. Are de asemenea perioada 6 daca dorim sa consideram ca este format din doua concatenari ale sirului „abcabc”.

Scrieti un program care determina cea mai scurta perioada a unui sir, precum si subsirurile curespunzatoare acesteia.

Date de intrare: In fisierul „cuvinte.in” se gasesc, cate unul pe linie, unul sau mai multe cuvinte (caracterele pot fi doar majuscule sau minuscule), lungimea unui cuvant fiind intotdeauna mai mica de 1000 caractere, iar numarul maxim de cuvinte dintr-un fisier este de 100.

Date de isesire: In fisierul de iesire „cuvinte.out” trebuie scrie, corespunzator fiecarei linii de intrare, intai perioada minima, apoi subsirul cerut.

• Exemplu:

cuvinte.in

HoHoHoHo
ComputerError
HiHaHoHiHaHo
cinecinecine
abcdabcdabcdabcd
CinCin

cuvinte.out

2 Ho
13 ComputerError
6 HiHaHo
4 cine
4 abcd
3 Cin

• Solutie

Vom parcurge toate numerele de la i la n (lungimea sirului)care sunt divizori ai lungimii (intr-un sir de lungime 15 nu putem avea perioada 4 de exemplu) si daca perioada este i ne oprim si afisam rezultatul. Conditia ca sirul de lungime i sa fie sirul-perioada corespunzator este s[0] = s[ i ] = s [ 2i ] = …., s[ n ] = s[ i+1 ] = s[ 2i+1 ] = …, s[ i-1 ] = s[ 2i-1 ]= … etc.

• Program:

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

char s[1001];
int i,k,n;
int main()
{
 ifstream f("cuvinte.in");
 ofstream g("cuvinte.out");
 while (!f.eof() )
 {
 f>>s;
 n=strlen(s);
 for (i=1;i<=n;++i)
 if (n%i==0)
 {
 for (k=i;k<=n;++k)
 if (s[k]!=s[k%i]) break;
 if (k==n) break;
 }
 s[i]='\0';
 g<<i<<" "<<s<<"\n";
 }
 f.close();
 g.close();
 return 0;
}