Cod sursa(job #2803246)

Utilizator alextmAlexandru Toma alextm Data 19 noiembrie 2021 18:16:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 2000005;
const int MAXP = 1000;

char a[MAXN], b[MAXN];
int urm[MAXN], pos[MAXP+1];

int main() {

  fin >> (a + 1) >> (b + 1);
  int n = strlen(a + 1);
  int m = strlen(b + 1);

  int x = 0;
  for(int i = 2; i <= n; i++) {
    while(x && a[x + 1] != a[i])
      x = urm[x];
    if(a[x + 1] == a[i])
      x++;
    urm[i] = x;
  }

  int k = 0;
  x = 0;

  for(int i = 1; i <= m; i++) {
    while(x && b[i] != a[x + 1])
      x = urm[x];

    if(b[i] == a[x + 1])
      x++;
    if(x == n) {
      k++;
      if(k <= MAXP)
        pos[k] = i - n;
    }
  }

  fout << k << "\n";
  for(int i = 1; i <= min(k, MAXP); i++)
    fout << pos[i] << " ";
  fout << "\n";

  return 0;
}