Guest User

Untitled

a guest
Jul 16th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.22 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. const int MAX_TAILLE = 50000;
  6.  
  7. int nbCar;
  8. bool chaine[MAX_TAILLE];
  9.  
  10. struct REP {
  11. int i, K, L;
  12. };
  13.  
  14. int main()
  15. {
  16. scanf("%d\n", &nbCar);
  17. for (int car = 0; car < nbCar; car++)
  18. {
  19. char c;
  20. scanf("%c", &c);
  21. getchar();
  22. chaine[car] = (c == 'a');
  23. }
  24.  
  25. REP best = {0, 1, 1};
  26. int nbCarSurDeux = nbCar/2;
  27. for (int taille = 1; taille <= nbCarSurDeux; taille++)
  28. {
  29.  
  30. int longueurRepetee = taille;
  31. int bestKFoisTaille = best.K * taille;
  32. int bestKPlusUnFoisTaille = bestKFoisTaille + taille;
  33.  
  34. if (bestKPlusUnFoisTaille > nbCar)
  35. break;
  36.  
  37. for (int i = taille; i <= nbCar; i++)
  38. {
  39.  
  40. if (i == nbCar || chaine[i] != chaine[i-taille])
  41. {
  42. if (longueurRepetee >= bestKPlusUnFoisTaille)
  43. {
  44. best.K = longueurRepetee / taille;
  45.  
  46. bestKFoisTaille = best.K * taille;
  47. bestKPlusUnFoisTaille = bestKFoisTaille + taille;
  48.  
  49. best.i = i - (bestKFoisTaille);
  50.  
  51. best.L = taille;
  52. }
  53. longueurRepetee = taille;
  54.  
  55. if (best.i + bestKFoisTaille > nbCar)
  56. break;
  57.  
  58. }
  59. else longueurRepetee++;
  60.  
  61. }
  62. }
  63.  
  64. printf("%d\n%d \n%d\n", best.K, best.L, best.i+1);
  65.  
  66. return 0;
  67. }
Add Comment
Please, Sign In to add comment