Cod sursa(job #1751948)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 2 septembrie 2016 13:53:15
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int main() {
  ifstream f("strmatch.in");
  ofstream g("strmatch.out");
  
  string pattern;
  string _template;
  
  f >> pattern >> _template;
  vector<int> sufPref = StringMatcher(pattern).matchString(_template);
  vector<int> occ;
  for(int i = 0; i < _template.size() - pattern.size(); i++) {
    if(sufPref[i + pattern.size() - 1] + 1 == pattern.size()) {
      occ.push_back(i);
    }
  }
  
  g << occ.size() << "\n";
  for(int i = 0; i <= min(1000, (int)occ.size() - 1); i++) g << occ[i] << " ";
  g << "\n";
  return 0;
}