kburnik

C++ - Palindromi - svi podpalindromi niza - sortirano

Nov 24th, 2012
123
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×