Cod sursa(job #2296703)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 4 decembrie 2018 22:34:21
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<fstream>
#include<cstring>
#include<string>
#include<map>
#define P 3
#define F 100007
#define G 100021
using namespace std;
ifstream cin("abc2.in");
ofstream cout("abc2.out");
char a[10000005];
int hashing[2][50005];
int n,m,k,h1,h2,p1,p2;
map<string,int> M;
string b;
long long ans;
int main(){
    cin>>a; ///cout<<a<<'\n';
    n=strlen(a);
    while(cin>>b){
        ///cout<<b<<'\n';
        if(M[b]==0){
            M[b]=1; ++m;
            for(int i=0;b[i];i++){
                hashing[0][m]=(hashing[0][m]*P+b[i])%F;
                hashing[1][m]=(hashing[1][m]*P+b[i])%G;
            }
        }
    }
    k=b.size(); p1=p2=1;
    ///cout<<n<<' '<<m<<' '<<k<<'\n';
    for(int i=1;i<k;i++){
        p1=(p1*P)%F;
        p2=(p2*P)%G;
    }
    for(int i=0;i<k;i++){
        h1=(h1*P+a[i])%F;
        h2=(h2*P+a[i])%G;
    }
    for(int i=1;i<=m;i++)
        if(hashing[0][i]==h1 && hashing[1][i]==h2) ++ans;
    for(int i=k;i<n;i++){
        h1=((h1-(a[i-k]*p1)%F+F)*P+a[i])%F;
        h2=((h2-(a[i-k]*p2)%G+G)*P+a[i])%G;
        for(int j=1;j<=m;j++)
            if(hashing[0][j]==h1 && hashing[1][j]==h2) ++ans;
    }
    cout<<ans;
}