Cod sursa(job #2028358)

Utilizator andru47Stefanescu Andru andru47 Data 27 septembrie 2017 19:33:43
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <bits/stdc++.h>
#define MOD1 666013
#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];
vector <int> H[666017];
inline bool hash_find(int masca1 , int masca2)
{
    for (auto &it : H[masca1])
        if (it == masca2)
            return true;
    return false;
}
inline void hash_insert(int masca1 , int masca2)
{
    H[masca1].push_back(masca2);
    return ;
}
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;
        }
        if (hash_find(masca1 , masca2) == true)
        {
            gets(sir + 1);
            continue;
        }
        hash_insert(masca1 , masca2);

        gets(sir + 1);
    }
    while (!feof(stdin));
    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 (hash_find(m1 , m2) == true)
            ok[i - l1 + 1] = true;
    }
    for (int i = 1; i<=len; ++i)
        ans += ok[i];
    printf("%d\n", ans);
    return 0;
}