Cod sursa(job #3036440)

Utilizator Danut200333Dumitru Daniel Danut200333 Data 24 martie 2023 12:37:33
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;
#define MOD1 10007
#define hash1 3
char A[10000001],B[10000001];
vector <unsigned int> hashtable[10007];
unsigned int sol,p1,p2,hashB1,hashA1,hashB2,hashA2,n,m;
bool search(unsigned int h)
{
    unsigned int poz=h%MOD1;
    for(unsigned int i=0; i<hashtable[poz].size(); ++i)if(hashtable[poz][i]==h)return 1;
    return 0;
}
int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    unsigned int i;
    scanf("%s", A);
    while(scanf("%s", B)!=EOF)
    {
        m=strlen(B);
        hashB1=0;
        for(i=0; i<m; ++i)
        {
            hashB1=((hashB1*hash1)+(B[i]-'a'));
        }
        if(!search(hashB1))hashtable[hashB1%MOD1].push_back(hashB1);
    }
    p1=p2=1;
    n=strlen(A);
    for(i=0; i<m; ++i)
    {
        hashA1=((hashA1*hash1)+(A[i]-'a'));
        if(i>0)
        {
            p1=(p1*hash1);
        }
    }
    if(search(hashA1))++sol;
    for(i=m; i<n; ++i)
    {
        hashA1=((hash1*(hashA1-((A[i-m]-'a')*p1))))+(A[i]-'a');
        if(search(hashA1))++sol;
    }
    printf("%d\n", sol);
    return 0;
}