Cod sursa(job #2417895)

Utilizator pickleVictor Andrei pickle Data 2 mai 2019 00:55:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
// String Match cu KMP
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
// const int INF = 0x3f3f3f3f;
const int Nmax = 2000666;

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

int N, M;
// A indexat de la 1.
// fie A_i,A_x prefixele stringului A de lungime i, respectiv x.
// pi[x] este cel mai mare i < x, astfel incat A_i, este sufix pentru A_x.
// pi[x] este 0 daca nici un prefix de-a lui A nu-i sufix pentru A_x.
// pi: {1..N} -> {0..N-1}
// pi[0] nu este definit (sau 0)
int pi[Nmax];
vector<int> result;

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

  // build the pi function
  int k;
  pi[1] = 0;
  for(int n = 2; n <= N; n++) {
    k = pi[n-1];
    // A_k is sufix for A_(n-1)
    while(k > 0 && A[n-1] != A[k]) {
      k = pi[k];
    }
    if (A[k] == A[n-1]) {
      k++;
    }
    pi[n] = k;
  }

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

  return 0;
}