Cod sursa(job #1375226)

Utilizator toranagahVlad Badelita toranagah Data 5 martie 2015 12:41:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
//Problem kmp
#include <cassert>
#include <cmath>
#include <cstdint>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

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

int main() {
  string pattern, text;
  fin >> pattern >> text;

  int n = text.size(), m = pattern.size();

  vector<int> pi(m);
  for (int i = 1, p = 0; i < m; i += 1) {
    while (p > 0 && pattern[i] != pattern[p]) p = pi[p];
    if (pattern[i] == pattern[p]) p += 1;
    pi[i] = p;
  }

  vector<int> match;
  for (int i = 0, p = 0; i < n; i += 1) {
    while (p > 0 && text[i] != pattern[p]) p = pi[p - 1];
    if (text[i] == pattern[p]) p += 1;

    if (p == m) {
      match.push_back(i - m + 1);
    }
  }

  fout << match.size() << '\n';
  for (int i = 0; i < 1000 && i < int(match.size()); i += 1) {
    fout << match[i] << ' ';
  }
  return 0;
}