Advertisement
kburnik

C++ - Palindromi - svi podpalindromi niza - sortirano

Nov 24th, 2012
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. // popis palindroma spremamo globalno
  8. vector < string > palindromi;
  9.  
  10. // niz je palindrom ako se jednako cita s obje strane i duljine >= 2
  11. bool palindrom(string s) {
  12.      int len = s.size();
  13.      // idemo do cjelobrojne polovice
  14.      for (int i = 0 ; i < len/2 ; i++) {
  15.          // ako se nasuprotni elementi ne poklapaju, niz nije palindrom
  16.          if (s[i] != s[len-i-1])
  17.             return false;
  18.      }
  19.      // niz je palindrom ako je duljine barem 2
  20.      return s.size() > 1;
  21. }
  22.  
  23.  
  24. // obrada: ako je s palindrom, dodaj ga na popis palindroma
  25. void obradi(string s) {    
  26.      if (palindrom(s)) palindromi.push_back(s);
  27. }
  28.  
  29. // kriterij usporedbe: prvo po duljini, zatim leksikografski
  30. int cmp (string a, string b){
  31.     if (a.size() == b.size())
  32.        return a < b;
  33.        
  34.     return a.size() < b.size();  
  35. }
  36.  
  37. int main () {
  38.    
  39.     string s;
  40.     cin >> s;
  41.    
  42.     // duljina niza
  43.     int len = s.size();
  44.    
  45.     // generiraj sve podnizove
  46.     for (int i = 0 ; i < len; i++) {
  47.         for (int j = 1; j <= (len - i) ; j++) {
  48.             // obradi pojedini podniz
  49.             obradi( s.substr(i,j) );
  50.         }
  51.     }
  52.  
  53.     // sortiraj popis palindroma po kriteriju duljine, zatim leksikografski
  54.     sort( palindromi.begin(), palindromi.end(), cmp );
  55.    
  56.     // ispisi sortirani popis palindroma
  57.     for (int i  = 0 ; i < palindromi.size(); i++) {
  58.         cout << palindromi[i] << endl;
  59.     }
  60.  
  61.     system ("pause");
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement