Cod sursa(job #2884350)

Utilizator smunteanuMunteanu Stefan Catalin smunteanu Data 2 aprilie 2022 22:22:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

static const int nmax = 2e6 + 2;

static char txt[nmax], pat[nmax];
static int n, m, lps[nmax];
vector<int> res;

void computeLPS() {
  
  int len = 0, i = 1;
  
  // for char in pattern
  while (i < m) {

    if (pat[len] == pat[i]) {
      lps[i++] = ++len;
      continue;
    }

    if (len) len = lps[len - 1];
    else i++;

  }
}

void kmpSearch() {

  int i = 0, j = 0; // txt & pat

  while (i < n) {
    if (txt[i] == pat[j]) i++, j++;
    if (j == m) res.push_back(i - m), j = lps[j - 1];
    else if (i < n && txt[i] != pat[j]) {
      if (j) j = lps[j - 1];
      else i++;
    }
  }
}

void kmp() {

  computeLPS();

  kmpSearch();

}

int main() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  ios_base::sync_with_stdio(false), cin.tie(NULL);
  
  cin >> pat >> txt;
  n = strlen(txt);
  m = strlen(pat);

  kmp();

  cout << res.size() << endl;
  for (int &k : res) cout << k << ' ';

}