Cod sursa(job #1814274)

Utilizator rangalIstrate Sebastian rangal Data 23 noiembrie 2016 20:11:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.81 kb
#include <stdio.h>
#include <string.h>
#define MAXN 2000001

#define P 62
#define MOD1 100007
#define MOD2 100021

char A[MAXN], B[MAXN];
int NA, NB;

int hashA1, hashA2, P1, P2;

//char match[MAXN];
int v[1003];

int Min(int a,int b)
{
   // return (a<b ? a:b);
   if(a<b) return a;
   return b;
}

int main()
{
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);

    scanf("%s %s", A, B);
    NA = strlen(A);
    NB = strlen(B);

    P1 = P2 = 1;
    hashA1 = hashA2 = 0;
    for (int i = 0; i < NA; i++)
    {
        hashA1 = (hashA1 * P + A[i]) % MOD1;
        hashA2 = (hashA2 * P + A[i]) % MOD2;

        if (i != 0)
            P1 = (P1 * P) % MOD1,
            P2 = (P2 * P) % MOD2;
    }

    if (NA > NB)
    {
        printf("0\n");
        return 0;
    }

    int hash1 = 0, hash2 = 0;
    for (int i = 0; i < NA; i++)
        hash1 = (hash1 * P + B[i]) % MOD1,
        hash2 = (hash2 * P + B[i]) % MOD2;

    //int Nr = 0;
    int ct=0;
    if (hash1 == hashA1 && hash2 == hashA2)
        //match[0] = 1, Nr++;
        ++ct,v[ct]=0;

    for (int i = NA; i < NB; i++)
    {
        hash1 = ((hash1 - (B[i - NA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
        hash2 = ((hash2 - (B[i - NA] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;

        if (hash1 == hashA1 && hash2 == hashA2)
            //match[ i - NA + 1 ] = 1, Nr++;
        {
            ++ct;
            if(ct<=1000) v[ct]=i-NA+1;
        }
    }
    //printf("%d\n", Nr);
    printf("%d\n",ct);

    /*Nr = 0;
    for (int i = 0; i < NB && Nr < 1000; i++)
        if (match[i])
            Nr++,
            printf("%d ", i);
    printf("\n");*/

    for(int i=1; i<= Min(1000,ct); ++i)
        printf("%d ",v[i]);

    return 0;
}
/*
1   0ms	248kb	OK	2	2
2	0ms	248kb	OK	2	2
3	0ms	272kb	OK	2	2
4	0ms	272kb	OK	2	2
5	0ms	272kb	OK	2	2
6	0ms	276kb	OK	2	2
7	0ms	272kb	OK	2	2
8	0ms	272kb	OK	2	2
9	0ms	268kb	OK	2	2
10	0ms	252kb	OK	2	2
11	0ms	268kb	OK	2	2
12	0ms	252kb	OK	2	2
13	0ms	276kb	OK	2	2
14	0ms	276kb	OK	2	2
15	0ms	252kb	OK	2	2
16	0ms	268kb	OK	2	2
17	0ms	268kb	OK	2	2
18	0ms	256kb	OK	2	2
19	0ms	252kb	OK	2	2
20	0ms	276kb	OK	2	2
21	40ms	1436kb	OK	2
22	68ms	2172kb	OK	2
23	56ms	1928kb	OK	2
24	44ms	1500kb	OK	2
25	36ms	1380kb	OK	2
26	64ms	2128kb	OK	2
27	56ms	1924kb	OK	2
28	44ms	1588kb	OK	2
29	48ms	1712kb	OK	2
30	68ms	2228kb	OK	2
31	68ms	2220kb	OK	2
32	60ms	2056kb	OK	2
33	52ms	1696kb	OK	2
34	64ms	2072kb	OK	2
35	68ms	2112kb	OK	2
36	36ms	1384kb	OK	2
37	64ms	2116kb	OK	2
38	52ms	1740kb	OK	2
39	44ms	1524kb	OK	2
40	48ms	1656kb	OK	2
41	56ms	1860kb	OK	2
42	44ms	1584kb	OK	2
43	56ms	1948kb	OK	2
44	60ms	1960kb	OK	2
45	48ms	1628kb	OK	2
46	40ms	1464kb	OK	2
47	52ms	1832kb	OK	2
48	64ms	2132kb	OK	2
49	116ms	4168kb	OK	2
50	68ms	2228kb	OK	2
*/