Cod sursa(job #2028179)

Utilizator andru47Stefanescu Andru andru47 Data 27 septembrie 2017 12:16:11
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>
#define MOD1 1003
#define MOD2 2017
#define mask1 27
#define mask2 29
using namespace std;
int pw[500005], pww[50005], ans, l1, len, ind = -1;
char s[10000005], sir[25];
bool ok[10000005];
int main() {
    //ifstream f("abc2.in");
    freopen("abc2.in" ,"r", stdin);
    freopen("abc2.out" ,"w", stdout);
    pw[0] = pww[0] = 1;
    for (int i = 1; i<=50000; ++i)
        pw[i] = (pw[i-1] * mask1) % MOD1, pww[i] = (pww[i - 1] * mask2) % MOD2;
    char chr = NULL;
    gets(s + 1);
    len = strlen(s + 1);
    gets(sir + 1);
    l1 = strlen(sir + 1);
    do {

        int masca1 = 0 , masca2 = 0;
        for (int i = 1; i<=l1; ++i) {
            masca1 = (masca1 * mask1 + sir[i]) % MOD1;
            masca2 = (masca2 * mask2 + sir[i]) % MOD2;
        }
        int m1 = 0, m2 = 0;
        for (int i = 1; i<=len; ++i) {
            if (i <= l1) {
                m1 = (m1 * mask1 + s[i]) % MOD1;
                m2 = (m2 * mask2 + s[i]) % MOD2;
            }
            if (i < l1)
                continue;
            if (i > l1) {
                m1 = ((m1 - (s[i - l1] * pw[l1 - 1]) % MOD1 + MOD1) * mask1 + s[i] ) % MOD1;
                m2 = ((m2 - (s[i - l1] * pww[l1 - 1]) % MOD2 + MOD2) * mask2 + s[i] ) % MOD2;
            }
            if (m1 == masca1 && m2 == masca2)
                ok[i - l1 + 1] = true;
        }

        gets(sir + 1);
    } while (!feof(stdin));
    for (int i = 1; i<=len; ++i)
        ans += ok[i];
    printf("%d\n", ans);
    return 0;
}