Cod sursa(job #1010139)

Utilizator andra23Laura Draghici andra23 Data 14 octombrie 2013 13:22:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <iostream>
#include <vector>

#define MAXN 2000010

using namespace std;

int t[MAXN];
vector <int> result;

void preprocess(string &w) {
  int i = 0, j = -1;
  t[i] = j;
  while (i < w.size()) {
    while (j >= 0 && w[i] != w[j]) j = t[j];
    ++i; ++j;
    t[i] = j;
  }
}

void search(string &w, string &s) {
  int i = 0, j = 0;
  while (i < s.size()) {
    while (j >= 0 && s[i] != w[j]) j = t[j];
    ++i; ++j;
    if (j == w.size()) {
      result.push_back(i-j);
      j = t[j];
    }
  }
}

int main() {
  string s, w;
  ifstream f("strmatch.in");
  ofstream g("strmatch.out");
  f >> w >> s;

  preprocess(w);
  result.clear();
  search(w, s);
  g << result.size() << endl;
  for (int i = 0; i < result.size(); ++i) {
    g << result[i] << " ";
  }

  return 0;
}