TopCoder SRM 502 Division 2 500 pts

SRM_502_Div2_500.cpp

#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

bool compare(string a, string b) {
  return a.length() < b.length();
}

class TheLotteryBothDivs {
 public:
  double find(vector<string> goodSuffixes) {
    double prob = 0;
    
    sort(goodSuffixes.begin(), goodSuffixes.end(), compare);
    goodSuffixes.resize( distance( goodSuffixes.begin(), unique(goodSuffixes.begin(), goodSuffixes.end()) ) );
    
    vector<string> suffixes = filter(goodSuffixes);
    
    for(auto p : suffixes) {
      prob += pow(0.1, p.length());
    }
    
    return prob;
  }
  
  vector<string> filter(vector<string> suffixes) {
    vector<string> filtered;
    
    for(auto p : suffixes) {
      bool found = false;
      for(auto q : filtered) {
        int pos = p.rfind(q);
        if( (pos != string::npos) && pos == (p.length()-q.length()) ) {
          found = true;
          break;
        }
      }
      if( !found )
        filtered.push_back(p);
    }
    
    return filtered;
  }
};