Cod sursa(job #977989)

Utilizator vlady1997Vlad Bucur vlady1997 Data 27 iulie 2013 13:06:09
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
        #include <cstdio>
        #include <cstring>
        #include <cmath>
        #define MAXN 2000001
        #define MOD1 666013
        #define MOD2 10003
        using namespace std;
        char s[MAXN], sub[MAXN];
        int a[MAXN];
        int hash1_sub (int m)
        {
            int h1=0;
            for (int i=0; i<m; i++) h1=(h1*101%MOD1+(int)sub[i])%MOD1; return h1;
        }
        int hash2_sub (int m)
        {
            int h2=0;
            for (int i=0; i<m; i++) h2=(h2*109%MOD2+(int)sub[i])%MOD2; return h2;
        }
        int hash1_s (int p, int m)
        {
            int h1=0;
            for (int i=p+0; i<p+m; i++) h1=(h1*101%MOD1+(int)s[i])%MOD1; return h1;
        }
        int hash2_s (int p, int m)
        {
            int h2=0;
            for (int i=p+0; i<p+m; i++)  h2=(h2*109%MOD2+(int)s[i])%MOD2; return h2;
        }
        int main()
        {
            freopen("strmatch.in","r",stdin);
            freopen("strmatch.out","w",stdout);
            gets(sub); gets(s); int m=strlen(sub); int n=strlen(s); int nr=0; int i;
            if (m>n) {printf("0"); return 0;}
            int hsub1=hash1_sub(m); int hsub2=hash2_sub(m); int p=pow(101,(m-1));
            int hs1=hash1_s(0,m); int hs2=hash2_s(0,m); int r=pow(109,(m-1));
            if(hs1==hsub1 && hs2==hsub2){nr++; a[nr]=0;}
            for (i=m; i<n; i++)
            {
                hs1=((hs1-(s[i-m]*p)%MOD1+MOD1)*101+s[i])%MOD1;
                hs2=((hs2-(s[i-m]*r)%MOD2+MOD2)*109+s[i])%MOD2;
                if(hs1==hsub1 && hs2==hsub2){nr++; a[nr]=i-m+1;}
            } printf("%d\n",nr);
            for (i=1; i<=nr; i++) if (i<=1000) printf("%d ",a[i]);
            fclose(stdin);
            fclose(stdout);
            return 0;
        }