Cod sursa(job #2449486)

Utilizator ejoi2019Ejoi 2019 ejoi2019 Data 19 august 2019 21:59:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 2000001;
const int L = 1000;
int p[N];
int sol[L], cnt;

int main() {
  freopen ("strmatch.in","r",stdin);
  freopen ("strmatch.out","w",stdout);

  string pat, s;
  cin >> pat >> s;
  int m = (int)pat.size(), n = (int)s.size();

  int j = 0;
  for (int i = 1; i < m; i++) {
    while (j && pat[i] != pat[j])
      j = p[j - 1];
    if (pat[i] == pat[j])
      j++;
    p[i] = j;
  }

  j = 0;
  for (int i = 0; i < n; i++) {
    while (j && s[i] != pat[j])
      j = p[j - 1];
    if (s[i] == pat[j])
      j++;
    if (j == m) {
      cnt++;
      if (cnt <= L)
        sol[cnt - 1] = i - j + 1;
      j = p[j - 1];
    }
  }

  cout << cnt << "\n";
  if (cnt > L)
    cnt = L;
  for (int i = 0; i < cnt; i++)
    cout << sol[i] << " ";

  cout << "\n";
  return 0;
}