Cod sursa(job #2546518)

Utilizator stef2003Bud Stefan stef2003 Data 14 februarie 2020 11:25:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char s1[2000001], s2[2000001];
int prefix[2000001], sol[2000001];
int main() {
  FILE *fin, *fout;
  int n, m, lc, i, nr;
  fin=fopen("strmatch.in","r");
  fout=fopen("strmatch.out","w");
  fscanf(fin, "%s\n%s",&s1,&s2);
  n=strlen(s1);
  m=strlen(s2);
  prefix[0]=-1;
  lc=-1;
  for(i=1;i<n;i++) {
    while(lc!=-1 && s1[i]!=s1[lc+1])
      lc=prefix[lc];
    if(s1[i]==s1[lc+1])
      lc++;
    prefix[i]=lc;
  }
  lc=-1;
  nr=0;
  for(i=0;i<m;i++) {
    while(lc!=-1 && s2[i]!=s1[lc+1])
      lc=prefix[lc];
    if(s2[i]==s1[lc+1]) {
      lc++;
      if(lc==n-1)
        sol[nr++]=i-n+1;
    }
  }
  fprintf(fout, "%d\n",nr);
  for(i=0;i<nr;i++)
    fprintf(fout, "%d ",sol[i]);
  return 0;
}