Cod sursa(job #1519441)

Utilizator edicCiuculescu Eduard edic Data 7 noiembrie 2015 12:39:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<cstdio>
#include<cstring>
using namespace std;
char s1[2000001],s2[2000001];
int n1=666013,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);
    int n,m,i,p1=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;
        kk1+=(s2[i]*p1)%n1;
        kk1%=n1;
        if(i)
        {
            p1=(p1*b)%n1;
        }
    }
    for(i=n;i<=m;i++)
    {
        if(k1==kk1)
        {
            if(verif(n,i-n)==1)
            {
                if(sum<=1000)
                {
                    sum++;
                    v[sum]=i-n;
                }
                else
                    sum++;
            }
        }
        kk1-=(s2[i-n]*p1)%n1;
        kk1%=n1;
        if(kk1<0)
        {
            kk1+=n1;
        }
        kk1=(kk1*b)%n1;
        kk1+=s2[i+1];
        kk1%=n1;
    }
    printf("%d\n",sum);
    for(i=1;i<=sum;i++)
    {
        printf("%d ",v[i]);
    }
    return 0;
}