Cod sursa(job #1519377)

Utilizator edicCiuculescu Eduard edic Data 7 noiembrie 2015 11:53:24
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<cstdio>
#include<cstring>
using namespace std;
char s1[2000001],s2[2000001];
int n1=666013,n2=100007,b=123,v[1002];
bool verif(int n,int i)
{
    int pp=1;
    for(int j=0;j<=n;j++)
    {
        if(s1[j]!=s2[j+i])
            pp=0;
    }
    return pp;
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    long long n,m,i,p1=1,p2=1,k1=0,k2=0,kk1=0,kk2=0,sum=0;
    scanf("%s%s",&s1,&s2);
    n=strlen(s1);
    n--;
    m=strlen(s2);
    m--;
    for(i=n;i>=0;i--)
    {
        k1+=(s1[i]*p1)%n1;
        k1%=n1;
        k2+=(s1[i]*p2)%n2;
        k2%=n2;
        kk1+=(s2[i]*p1)%n1;
        kk1%=n1;
        kk2+=(s2[i]*p2)%n2;
        kk2%=n2;
        if(i)
        {
            p1=(p1*b)%n1;
            p2=(p2*b)%n2;
        }
    }
    for(i=n+1;i<=m;i++)
    {
        if(k1==kk1&&k2==kk2)
        {
            if(verif(n,i-n-1)==1)
            {
                if(sum<=1000)
                {
                    sum++;
                    v[sum]=i-n-1;
                }
            }
        }
        kk1-=(s2[i-n-1]*p1)%n1;
        kk1%=n1;
        if(kk1<0)
        {
            kk1+=n1;
        }
        kk2-=(s2[i-n-1]*p2)%n2;
        kk2%=n2;
        if(kk2<0)
        {
            kk2+=n2;
        }
        kk1=(kk1*p1)%n1;
        kk1+=s2[i];
        kk1%=n1;
        kk2=(kk2*p2)%n2;
        kk2+=s2[i];
        kk2%=n2;
    }
    printf("%d\n",sum);
    for(i=1;i<=sum;i++)
    {
        printf("%d ",v[i]);
    }
    return 0;
}