Cod sursa(job #2418446)

Utilizator pickleVictor Andrei pickle Data 5 mai 2019 00:44:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 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 = 1333;

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) {
  pi[1] = 0;
  int k = 0;
  for (int n = 2; n <= A.length(); n++) {
    while(k > 0 && A[n-1] != A[k]) {
      k = pi[k];
    }
    if (A[n-1] == A[k]) { k++; }
    pi[n] = k;
  }
}

vi answer;

int main(void) {
  string A, B;
  fin >> A >> B;

  build_pi(pi, A);

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

  return 0;
}