Cod sursa(job #2385007)

Utilizator aditzu7Adrian Capraru aditzu7 Data 21 martie 2019 14:54:09
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
#include <string.h>
using namespace std;
int sol,n,m;
int i,p1=127,p2=13;
unsigned int pp=1;
char s[2000005];
unsigned int pp1,pp2,x1,y1,x2,y2;
int ssol[2000005];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s",s);
    int k=strlen(s);
    pp1=pp2=1;
    for(i=0;i<strlen(s);i++){

     x1=x1*p1+s[i];
     x2=x2*p2+s[i];
    pp1*=p1;
    pp2*=p2;

    }
    pp1/=p1;
    pp2/=p2;
    scanf("%s",s);
    for(i=0;i<=k-1;i++){
    y1=y1*p1+s[i];
    y2=y2*p2+s[i];

    }
    if(y1==x1&&y2==x2) {sol++;ssol[sol]=0;}
    for(i=k;i<strlen(s);i++){
     y1=p1*(y1-s[i-k]*pp1)+s[i];
     y2=p2*(y2-s[i-k]*pp2)+s[i];
     if(x1==y1&&x2==y2) {sol++;ssol[sol]=i-k+1;}



    }

    printf("%d\n",sol);
    for(i=1;i<=sol;i++) printf("%d ",ssol[i]);
        return 0;
}