Cod sursa(job #1468989)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 7 august 2015 14:22:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <cstring>
#define LMAX 2000007
#define MOD 100007
#define MOD2 100927
using namespace std;
char a[LMAX],b[LMAX];
int p[LMAX],p2[LMAX],h1[1005],cat;
int main()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    scanf("%s",a);
    scanf("%s",b);
    int p1=strlen(a);
    int pl2=strlen(b);
    p[0]=1;
    p2[0]=1;
    for(int i=1;i<p1;i++)
    {
        p[i]=p[i-1]*74;
        p[i]%=MOD;
        p2[i]=p2[i-1]*74;
        p2[i]%=MOD2;
    }
    int val=0,val2=0,key=0,key2=0;
    for(int i=0;i<p1;i++)
    {
        val+=(long long)p[p1-i-1]*(a[i]-'0');
        val%=MOD;
        val2+=(long long)p2[p1-i-1]*(a[i]-'0');
        val2%=MOD2;
        key+=(long long)p[p1-i-1]*(b[i]-'0');
        key2+=(long long)p2[p1-i-1]*(b[i]-'0');
        key%=MOD;
        key2%=MOD2;
    }
    if(val2==key2&&val==key) h1[++cat]=0;
    for(int i=p1;i<pl2;i++)
    {
        key=key-((long long)(p[p1-1]*(b[i-p1]-'0'))%MOD)+MOD;
        key2=key2-((long long)(p2[p1-1]*(b[i-p1]-'0'))%MOD2)+MOD2;
        key*=74;
        key%=MOD;
        key2*=74;
        key2%=MOD2;
        key+=(b[i]-'0');
        key2+=(b[i]-'0');
        key%=MOD;
        key2%=MOD2;
        if(val2==key2&&val==key&&cat<1000) h1[++cat]=i-p1+1;
        //printf("%lld\n",key);
    }
    printf("%d\n",cat);
    for(int i=1;i<=cat;i++) printf("%d ",h1[i]);
}