• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Problema Siruri Periodice

5
  • Publicat de Coss
  • în Probleme algoritmică
  • — 5 oct., 2009 at 4:58 pm

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”. 2679427824_0ac3c937aa

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;
}

Etichete: C++informaticaOlimpiadaprobleme algoritmicasiruri periodice

— Albulescu Cosmina a scris 223 articole

Nu există o descriere a autorului.

  • Articolul anterior New PSP Go
  • Articolul următor Un certificat SSL de Paypal a fost publicat

5 Comentarii

  1. Andrei Misarca spune:
    octombrie 5, 2009 la 6:54 pm

    Problema se poate face si in O(N) cu ajutorul algoritmului de determinare a prefixului, parte din KMP.

  2. miculprogramator spune:
    octombrie 5, 2009 la 6:56 pm

    N fiind numarul de cuvinte din fisier? 😕

  3. Andrei Misarca spune:
    octombrie 5, 2009 la 6:58 pm

    Lungimea fiecarui cuvant. 🙂 Ma refeream la un singur cuvant 😀

  4. miculprogramator spune:
    octombrie 5, 2009 la 7:05 pm

    Oh God, pe ce planeta sunt? :)) Scuza-mi intrebarea busita.

  5. Andrei Misarca spune:
    octombrie 5, 2009 la 8:29 pm

    Intrebarea a fost pusa bine, eu m-am exprimat gresit.


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • martie 2021
    L Ma Mi J V S D
    1234567
    891011121314
    15161718192021
    22232425262728
    293031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Probleme algoritmică
  • Problema Siruri Periodice
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons