Cod sursa(job #2417536)

Utilizator aditzu7Adrian Capraru aditzu7 Data 30 aprilie 2019 12:06:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <string.h>
using namespace std;
unsigned int i,sol,n,m;
unsigned int p1=127,p2=13;
char s[2000005];
unsigned int pp1,pp2,x1,y1,x2,y2;
unsigned int ssol[2000005];

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

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

        x1=x1*p1+s[i];
        x2=x2*p2+s[i];
      if(i!=0){ 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;
    }
    int n=strlen(s);
    for(i=k; i<n; 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("%u\n",sol);
    for(i=1; i<=sol&&i<=1000; i++) printf("%u ",ssol[i]);
    return 0;
}