Cod sursa(job #977945)

Utilizator vlady1997Vlad Bucur vlady1997 Data 27 iulie 2013 11:11:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
        #include <cstdio>
        #include <cstring>
        #define MAXN 2000001
        #define MOD 666013
        using namespace std;
        char s[MAXN], sub[MAXN];
        int a[MAXN];
        int hash_sub (int m)
        {
            int h1=0;
            for (int i=0; i<m; i++)
            {
                h1=(h1*101%MOD+(int)sub[i])%MOD;
            }
        }
        int hash_s (int p, int m)
        {
            int h1=0;
            for (int i=p+0; i<p+m; i++)
            {
                h1=(h1*101%MOD+(int)s[i])%MOD;
            }
        }
        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;
            int hsub=hash_sub(m);
            int hs=hash_s(0,m);
            for (i=0; i<n-m+1; i++)
            {
                if (hs==hsub)
                {
                    if (!strncmp(s+i,sub,m)) {nr++; a[nr]=i;}
                    hs=hash_s(i,m);
                }
            } printf("%d\n",nr);
            for (i=1; i<=nr; i++) printf("%d ",a[i]);
            fclose(stdin);
            fclose(stdout);
            return 0;
        }