Cod sursa(job #2418449)

Utilizator pickleVictor Andrei pickle Data 5 mai 2019 00:50:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
#define repa(i, l, r) for (int i = l; i < r; i++)
#define repd(i, r, l) for (int i = r; i > l; i--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int Nmax = 2000666;

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

int pi[Nmax];

// builds the KMP prefix function for the string A.
void build_pi(int* const pi, const string &A) {
  int N = A.length();

  pi[1] = 0;
  int k = 0;
  for (int n = 1; n < N; n++) {
    while(k > 0 && A[n] != A[k]) {
      k = pi[k];
    }
    if (A[n] == A[k]) {
      k++;
    }
    pi[n+1] = k;
  }
}

vi answer;

int main(void) {
  string A, B;
  fin >> A >> B;
  int N = A.length();
  int M = B.length();
  build_pi(pi, A);

  int count = 0;
  int k = 0;
  for(int n = 0; n < M; n++) {
    while(k > 0 && B[n] != A[k]) {
      k = pi[k];
    }
    if (B[n] == A[k]) {
      k++;
    }
    if (k == N) {
      k = pi[N];
      if (count < 1000) {
        answer.push_back(n - N + 1);
      }
      count++;
    }
  }
  fout << count << "\n";
  for(int pos: answer) {
    fout << pos << ' ';
  }
  fout << endl;

  return 0;
}