Cod sursa(job #2595897)

Utilizator avtobusAvtobus avtobus Data 8 aprilie 2020 16:46:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
// redo strmatch using KMP (Knuth-Morris-Pratt)
#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;
string A, B;

/*
* pi: prefix function: [1,N] -> [0,N-1]
*   both the argument and the value for pi are the string length, not the string position.
*   pi[n] < n
*/

int pi[Nmax];

// Todo: pass A and pi as arguments (by reference) to build_prefix()
void build_prefix() {
  rep(i, A.size()) {
    // we want to determine pi[i+1] (prefix for the substring that ends in A[i])
    // we know pi[i] by induction
    int k = pi[i]; // yhis means that A[i-1] == A[k-1];
    while(k > 0 && A[i] != A[k]) {
      k = pi[k];
    }
    if (i == 0 || A[i] != A[k]) {
      pi[i+1] = 0;
    } else {
      pi[i+1] = k+1;
    }
  }
}

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

  build_prefix();
  int count = 0, k = 0;
  vi res;
  rep(i, M) {
    while(k > 0 && B[i] != A[k]) {
      k = pi[k];
    }
    if (B[i] == A[k]) {
      k++;
    }
    if (k == N) {
      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;
}