Cod sursa(job #2276361)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 4 noiembrie 2018 17:16:30
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdlib.h>
#include <stdio.h>
#include <cstring>
#include <algorithm>

#define MAXC 2000001

using namespace std;

const int MAXP = 1001;

char A[MAXC];
char B[MAXC];

int pt[MAXC];

int ret[MAXP];

int lg, lgc, c;


void p() {
   for (int i=2, q=0; i <= lgc; ++i) {
      for (;q != 0 && B[q+1] != B[i]; q = pt[q]);
      if (B[q+1] == B[i]) q++;
      pt[i] = q;
   }
}

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

   scanf("%s", B+1);
   lgc = strlen(B+1);

   scanf("%s", A+1);
   lg = strlen(A+1);


   for (int i = 0; i <= lgc; ++i) {
      pt[i] = 0;
   }

   p();

   c = 0;

   for (int i=1, q=0; i <= lg; ++i) {
      for (;q != 0 && A[i] != B[q+1]; q = pt[q]);
      if (B[q+1] == A[i]) q++;
      if (q == lgc) {
        ret[c++] = i - lgc;
      }
   }

   printf("%d\n", c);
   for (int i = 0; i < min(c,MAXP); ++i) {
      printf("%d ", ret[i]);
   }

   return 0;
}