Cod sursa(job #1751964)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 2 septembrie 2016 14:23:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <algorithm>

using namespace std;

class StringMatcher {
  public:
    StringMatcher(string const &s):
     pattern(s) {
      sufPref = vector<int>(pattern.size());
      sufPref[0] = 0;
      for(int i = 1, match = 0; i < pattern.size(); i++) {
        while(match > 0 && pattern[match] != pattern[i]) {
          match = sufPref[match - 1];
        }
        if(pattern[match] == pattern[i]) {
          match++;
        }
        sufPref[i] = match;
      }
    }
    vector<int> findOccurrences(string const& _template) {
      vector<int> _templateSufPref = matchString(_template);
      vector<int> oc;
      for(int i = 0; i < _template.size(); i++) {
        if(_templateSufPref[i] == pattern.size()) {
          oc.push_back(i - pattern.size() + 1);
        }
      }
      if(oc.size() > 1000) {
        oc.erase(oc.begin() + 1000, oc.end());
      }
      return oc;
    }
  private:
    vector<int> matchString(string const& _template) {
      vector<int> _templateSufPref(_template.size());
      for(int i = 0, match = 0; i < _template.size(); i++) {
        while(match > 0 && pattern[match] != _template[i]) {
          match = sufPref[match - 1];
        }
        if(pattern[match] == _template[i]) {
          match++;
        }
        _templateSufPref[i] = match;
      }
      return _templateSufPref;
    }
    vector<int> sufPref;
    string pattern;
};

int main() {
  ifstream f("strmatch.in");
  ofstream g("strmatch.out");
  string pattern, _template;
  f >> pattern >> _template;
  vector<int> oc = StringMatcher(pattern).findOccurrences(_template);
  g << oc.size() << "\n";
  for(auto o : oc) g << o << " ";
  g << "\n";
  return 0;
}