Cod sursa(job #2556036)

Utilizator ivddabDabelea Ioana-Viviana ivddab Data 24 februarie 2020 17:20:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <cstring>
#define NM 2000002
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,l;
int nr[NM],urm[NM];
char s1[NM],s2[NM];
void prefix(int n,char s1[]){
  int i,j;
  urm[0]=0; j=-1;
  for(i=1;i<n;i++){
    while(j>0&&s1[j+1]!=s1[i]) j=urm[j];
    if(s1[j+1]==s1[i]) j++;
    urm[i]=j;
  }
}
int main()
{
    f>>s1>>s2;
    n=strlen(s1); m=strlen(s2);
    prefix(n,s1);
    int i,j;
    j=-1;
    for(i=0;i<m&&l<1000;i++){
        while(j>0&&s1[j+1]!=s2[i]) j=urm[j];
        if(s1[j+1]==s2[i]) j++;
        if(j==n-1&&l<1000){ nr[++l]=i-n+1;
          j=urm[j];
        }
    }
    g<<l<<'\n';
    for(i=1;i<=l;i++)
        g<<nr[i]<<' ';
    return 0;
}