Cod sursa(job #895491)

Utilizator cremarencodianaCremarenco Diana cremarencodiana Data 27 februarie 2013 11:35:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
# include <cstring>
# define b1 27
# define b2 29
# define mod1 10007
# define mod2 666013
using namespace std;
int n,m,i,p1,p2,v1,v2,h1,h2,nr,nr1;
char s[2000010],str[2000010];
bool match[2000010];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s",s,str);

    m=strlen(s);
    n=strlen(str);
    p1=p2=1;

    if (m>n)
    {
        printf("%d\n",0);
        return 0;
    }

    for (i=0; i<m; i++)
    {
        v1=(v1*b1+s[i])%mod1;
        v2=(v2*b2+s[i])%mod2;
        if (i!=1)
        {
            p1=(p1*b1)%mod1;
            p2=(p2*b2)%mod2;
        }
    }

    for (i=0; i<m; i++)
    {
        h1=(h1*b1+str[i])%mod1;
        h2=(h2*b2+str[i])%mod2;
    }
    if (h1==v1 && h2==v2)
    {
        nr++;
        match[0]=true;
    }

    for (i=m; i<n; i++)
    {
        h1=((h1-(str[i-m]*p1)%mod1+mod1)*b1+str[i])%mod1;
        h2=((h2-(str[i-m]*p2)%mod2+mod2)*b2+str[i])%mod2;
        if (h1==v1 && h2==v2)
        {
            nr++;
            match[i-m+1]=true;
        }
    }
    printf("%d\n",nr);

    for (i=0; i<n && nr1<1000; i++)
        if (match[i]==true)
        {
            nr1++;
            printf("%d ",i);
        }
    printf("\n");
    return 0;
}