Cod sursa(job #1166530)

Utilizator toranagahVlad Badelita toranagah Data 3 aprilie 2014 17:31:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define len(x) int((x).size())

vector<int> res;
vector<int> pi;

void compute_prefix(const string &s);
void find_match(const string &s, const string &t);

int main() {
  string P, T;
  fin >> P >> T;
  P = " " + P;
  T = " " + T;

  compute_prefix(P);
  find_match(P, T);

  fout << len(res) << '\n';
  for (int i = 0; i < len(res) && i < 1000; i += 1) {
    fout << res[i] << ' ';
  }
}

void compute_prefix(const string &s) {
  int n = len(s) - 1;
  pi.resize(n + 1);

  for (int i = 2, p = 0; i <= n; i += 1) {
    while (p > 0 && s[i] != s[p + 1]) p = pi[p];
    if (s[i] == s[p + 1]) p += 1;
    pi[i] = p;
  }
}

void find_match(const string &s, const string &t) {
  int n = len(t) - 1, m = len(s) - 1;

  for (int i = 1, p = 0; i <= n; i += 1) {
    while (p > 0 && s[p + 1] != t[i]) p = pi[p];
    if (s[p + 1] == t[i]) p += 1;
    if (p == m) {
      res.push_back(i - m);
    }
  }
}