Cod sursa(job #1166555)

Utilizator toranagahVlad Badelita toranagah Data 3 aprilie 2014 17:42:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 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())
const int MAX_N = 2e6 + 100;

string P, T;
vector<int> pi, ans;

void kmp();

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

  kmp();

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

void kmp() {
  int n = len(T) - 1, m = len(P) - 1;
  pi.resize(len(P));

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

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