• 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 Fără categorie
  • — 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;
}

Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!

— 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

    • imacoolat-curat.ro
      | Published: februarie 3, 2020 - 2:00 am
    • hotel-palace.ro
      | Published: februarie 2, 2020 - 2:00 am
    • www.tahometru.ro
      | Published: februarie 1, 2020 - 2:00 am
    • alexisart.ro
      | Published: ianuarie 30, 2020 - 2:00 am
    • justshop.ro
      | Published: ianuarie 29, 2020 - 2:00 am
    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
  • ianuarie 2021
    L Ma Mi J V S D
    « dec.    
     123
    45678910
    11121314151617
    18192021222324
    25262728293031
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • 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

Multumim foarte mult ca ne-ai raportat greseala! O vom remedia in cel mai scurt timp posibil.