Cod sursa(job #1818087)

Utilizator geni950814Geni Geni geni950814 Data 28 noiembrie 2016 20:15:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

string in1;
string in2;
string sub = " ";
string str = " ";

void prefix(const string &sub, vector<int> &pi) {
  int curr = 0;
  for (size_t i = 2; i < sub.length(); i++) {
    while(curr > 0 && sub[i] != sub[curr + 1]) {
      curr = pi[curr];
    }
    if(sub[i] == sub[curr + 1]) {
      curr++;
    }
    pi.push_back(curr);
  }
}

void KMP(const string &sub, const string &str, const vector<int> &pi, vector<int> &result) {
  int curr = 0;
  int sub_length = sub.size();
  for (size_t i = 1; i < str.length(); i++) {
    while(curr > 0 && sub[curr + 1] != str[i]) {
      curr = pi[curr];
    }
    if(sub[curr + 1] == str[i]) {
      curr++;
    }
    if(curr == sub_length - 1) {
      if (result.size() < 1000) {
        result.push_back(i - curr + 1);
      }
      curr = pi[curr];
    }
  }
}



int main() {
  ifstream in("strmatch.in");
  ofstream out("strmatch.out");
  in >> in1 >> in2;
  sub.append(in1);
  str.append(in2); 
  vector<int> pi(2);
  prefix(sub, pi);
  vector<int> result;
  KMP(sub, str, pi, result);
  
  int count = result.size();
  
  out << count << "\n";
  for (int i : result) {
    out << i - 1 << " ";
  }
  return 0;
}