Cod sursa(job #976517)

Utilizator OnimushaLordTiberiu Copaciu OnimushaLord Data 23 iulie 2013 13:22:32
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
# include <cstdio>
# include <cstring>
# include <cmath>
# define MAXN 2000001
# define K 666013
# define Q 10003
using namespace std;
int v1,v2,h1,h2;
int n,i,m,nr;
int P,R,s[MAXN],x;
char a[MAXN],b[MAXN];
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    gets(b);
    gets(a);
    m=strlen(b);
    n=strlen(a);
    P=pow(101,m-1);
    R=pow(109,m-1);
    h1=(b[0]*101*101+b[1]*101+b[2])%K;
    h2=(b[0]*109*109+b[1]*109+b[2])%Q;
    v1=(a[0]*101*101+a[1]*101+a[2])%K;
    v2=(a[0]*109*109+a[1]*109+a[2])%Q;
    if(h1==v1 && h2==v2) nr++;
    for(i=m; i<n; ++i)
    {
        v1 =  ( (v1 - (a[ i - m]*P)% K + K)*101 + a[i])%K;
        v2 =  ( (v2 - (a[ i - m]*R)% Q + Q)*109 + a[i])%Q;
        if(v1==h1 && v2==h2)
        {
            nr++;
            s[++x]=i-m+1; s[0]++;
        }
    }
    printf("%d\n", nr);
    for(i=1; i<=s[0]; ++i) printf("%d ", s[i]);
    return 0;
}