Cod sursa(job #2487256)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 4 noiembrie 2019 13:19:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include<cstdio>
#include<cstring>
const int RMAX = 1000;
const int LMAX = 2000000;
char P[1 + LMAX + 1];
char T[LMAX + 1];
int v[RMAX + 1];
int lps[LMAX + 1];
int main()
{
    freopen("strmatch.in" , "r" , stdin);
    freopen("strmatch.out" , "w" , stdout);
    scanf("%s" , P + 1);
    scanf("%s" , T);
    int n = strlen(P + 1);
    int m = strlen(T);
    lps[0] = 0;
    lps[1] = 0;
    for (int i = 2; i <= n; i++) {
        int x = lps[i - 1];
        while (x > 0 && P[x + 1] != P[i]) {
          x = lps[x];
        }
        if (P[x + 1] == P[i]) {
          lps[i] = x + 1;
        } else {
          lps[i] = 0;
        }
  }
  int x = 0 , contor = 0 ;
  for (int i = 0; i < m; i++) {
    while (x > 0 && P[x + 1] != T[i]) {
      x = lps[x];
    }
    if (P[x + 1] == T[i]) {
      x++;
    } else {
      x = 0;
    }
    if (x == n) {

        contor ++;
        if(contor <= 1000){
        v[contor] = i;
        }
    }
  }
  printf("%d\n" , contor);
  if(contor > 1000)
    contor = 1000;
  for(int i = 1; i <= contor ; i ++)
  {
      printf("%d " , v[i] - n + 1);
  }
  return 0;
}