Cod sursa(job #1146336)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 18 martie 2014 21:20:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define Nmax 2000005
#define P1 (1<<30)
#define P2 (1<<26)
#define X 123456
#define Y 654321

using namespace std;

char a[Nmax],b[Nmax];
int sol[Nmax];

int main()
{
    int N,M,v1=0,v2=0,v3=0,v4=0,aux1=1,aux2=1,i;
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    scanf("%s%s", (a+1),(b+1));
    N=strlen(a+1); M=strlen(b+1);
    for(i=1;i<=N;++i)
    {
        v1=((1LL*v1*X+a[i]-'0')&(P1-1));
        v2=((1LL*v2*Y+a[i]-'0')&(P2-1));
    }
    for(i=1;i<=N;++i)
    {
        v3=((1LL*v3*X+b[i]-'0')&(P1-1));
        v4=((1LL*v4*Y+b[i]-'0')&(P2-1));
    }
    for(i=1;i<N;++i)
    {
        aux1=((1LL*aux1*X)&(P1-1));
        aux2=((1LL*aux2*Y)&(P2-1));
    }
    if(v3==v1 && v4==v2)
        sol[++sol[0]]=0;
    for(i=N+1;i<=M;++i)
    {
        v3=((((v3-((1LL*(b[i-N]-'0')*aux1)&(P1-1))+P1)&(P1-1))*X+b[i]-'0')&(P1-1));
        v4=(((((v4-(1LL*(b[i-N]-'0')*aux2)&(P2-1))+P2)&(P2-1))*Y+b[i]-'0')&(P2-1));
        if(v3==v1 && v4==v2)
            sol[++sol[0]]=i-N;
    }
    printf("%d\n", sol[0]);
    for(i=1;i<=sol[0] && i<=1000;++i)
        printf("%d ", sol[i]);
    printf("\n");
    return 0;
}