Cod sursa(job #1010138)

Utilizator andra23Laura Draghici andra23 Data 14 octombrie 2013 13:18:36
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <iostream>
#include <vector>

#define MAXN 2000010

using namespace std;

int t[MAXN];

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;
  }
}

vector<int> search(string &w, string &s) {
  vector <int> result;
  int i = 0, j = -1;
  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];
    }
  }
  return result;
}

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

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

  return 0;
}