Cod sursa(job #2418348)

Utilizator pickleVictor Andrei pickle Data 4 mai 2019 17:46:43
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];
vi answer;

int main(void) {
  string A, B;
  fin >> A >> B;
  int N = A.length();
  int M = B.length();
  A = "_" + A;
  B = "_" + B;

  // build pi
  int k;
  pi[0] = pi[1] = 0;
  for(int i = 2; i <= N; i++) {
    k = pi[i-1];
    while(k > 0 && A[i] != A[k+1]) {
      k = pi[k];
    }
    if (A[i] == A[k+1]) {
      k++;
    }
    pi[i] = k;
  }

  int count = 0;
  // compute matches
  k = 0;
  for(int i = 1; i <= M; i++) {
    while(k > 0 && B[i] != A[k+1]) {
      k = pi[k];
    }
    if (B[i] == A[k+1]) {
      k++;
    }
    if (k == N) {
      if (count < 1000) {
        answer.push_back(i - N + 1 - 1); // answers should be 0-indexed.
      }
      count++;
      k = pi[k];
    }
  }
  fout << count << '\n';
  if (count > 0) {
    for(int i: answer)
      fout << i << ' ';
    fout << endl;
  }

  return 0;
}