Cod sursa(job #2596019)

Utilizator avtobusAvtobus avtobus Data 9 aprilie 2020 00:18:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
// redo strmatch with KMP(Knuth-Morris-Pratt), but use 0-based indexing for the prefix function (for consistency)
#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;
typedef vector<int> vi;
const int INF = 0x3f3f3f3f;

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

const int Nmax = 2000666;

/*
* pi - the prefix function: [0, N-1] -> [-1, N-2]
    the argument - is the current position in string A.
    the value is the corresponding position in A or -1 if no prefix of A is a suffix ending in current position.
    for all n, pi[n] < n.
*/
int pi[Nmax];
int N, M;
string A,B;

void build_prefix() {
  pi[0] = -1;
  int k = -1;
  // k -> the current accepted state; the position of the current largest prefix (just before starting the current iteration)
  for(uint i = 1; i < A.size(); i++) {
    while(k > -1 && A[i] != A[k+1]) { k = pi[k]; }

    if (A[i] == A[k+1]) { k++; }

    pi[i] = k;
  }
}

int main(void) {
  fin >> A >> B;
  N = A.size();
  M = B.size();
  if (N > M) {
    fout << "0\n";
    return 0;
  }

  build_prefix();
  int k = -1;
  int count = 0;
  vi res;
  rep(i, M) {
    while(k > -1 && B[i] != A[k+1]) { k = pi[k]; }
    if (B[i] == A[k+1]) { k++; }
    if (k == N-1) {
      count++;
      if (count <= 1000) {
        res.push_back(i-(N-1));
      }
      k = pi[k];
    }
  }

  fout << count << '\n';
  for(auto pos: res) {
    fout << pos << ' ';
  }
  fout << endl;

  return 0;
}