Cod sursa(job #983995)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 13 august 2013 10:38:36
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<cstdio>
#include<cstring>
//#define mod1 100007
//101
//#define mod2 100021
//109
using namespace std;
int min(int a, int b){if (a<=b) return a; else return b;}
int i, v1, v2, val1, val2, p1, p2, pt1, pt2, n, n2, nr, a[2000001];
char s[2000001], s2[2000001];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    nr=0;
    gets(s);
    n=strlen(s);
    p1=1;
    p2=1;
    v1=0;
    v2=0;
    for (i=n-1; i>=0; i--)
    {
        v1=(v1+(int)s[i]*p1)%100007;
        v2=(v2+(int)s[i]*p2)%100021;
        if (i>0)
        {
            p1=(p1*101)%100007;
            p2=(p2*109)%100021;
        }
    }
    gets(s2);
    n2=strlen(s2);
    pt1=1;
    pt2=1;
    val1=0;
    val2=0;
    if (n2<n)
    {
        printf("0\n");
        return 0;
    }
    for (i=n-1; i>=0; i--)
    {
        val1=(val1+(int)s2[i]*pt1)%100007;
        val2=(val2+(int)s2[i]*pt2)%100021;
        if (i>0)
        {
            pt1=(pt1*101)%100007;
            pt2=(pt2*109)%100021;
        }
    }
    if ((v1==val1)&&(v2==val2))
    {
        nr++;
        a[++a[0]]=0;
    }
    for (i=n; i<n2; i++)
    {
        val1=val1-((int)s2[i-n]*p1)%100007 + 100007;
        val1=(val1*101+s2[i])%100007;

        val2=val2-((int)s2[i-n]*p2)%100021 + 100021;
        val2=(val2*109+s2[i])%100021;
        if ((v1==val1)&&(v2==val2))
        {
            nr++;
            a[++a[0]]=i-n+1;
        }
    }
    printf("%d\n", nr);
    for (i=1; i<=min(a[0] 1000); i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}