Cod sursa(job #659140)

Utilizator razvan_kusztosKusztos razvan razvan_kusztos Data 10 ianuarie 2012 10:44:44
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#define m1 127
#define m2 131
#define mod 666013
using namespace std;
int a[100],b[100],i,j,nr,n,sol,h1,h2,v1,v2,p1,p2;
char chr;
int pow(int a,int b)
{
    if (b==0) return 1;
    if (b%2==0) {
        int aux=pow(a,b/2);
        return (aux*aux)%mod;
        }
    else
    if (b%2==1) return a*pow(a,b-1)%mod;
}

int main()
    {
        freopen("strmatch.in","r",stdin);
        freopen("strmatch.out","w",stdout);
        while (1==1)
        {
             scanf("%c",&chr);
             if (chr=='\n') break;
             h1=(h1*m1+chr)%mod;
             h2=(h2*m2+chr)%mod;
             nr++;
        }
        while (1==1)
        {
            scanf("%c",&chr);
            if (chr=='\n') break;
            a[++n]=(int)chr;
        }
        for (i=1 ;i<=nr;i++)
           {
                v1=(v1*m1+a[i])%mod;
                v2=(v2*m2+a[i])%mod;
           }
        p1=pow(m1,nr-1);
        p2=pow(m2,nr-1);
        if (v1==h1 && h2==v2) {sol++;b[sol]=0;}
        for (i=nr+1;i<=n;i++)
        {
            v1=((v1-(a[i-nr]*p1)%mod+mod)%mod*m1+a[i])%mod;
            v2=((v2-(a[i-nr]*p2)%mod+mod)%mod*m2+a[i])%mod;
            if (v1==h1 && h2==v2) {sol++;b[sol]=i-nr;}
        }
        printf("%d\n",sol);
        if (sol<=1000) for (i=1 ;i<=sol;i++) printf("%d ",b[i]);
           else for (i=1;i<=1000;i++) printf("%d",b[i]);
    }