Cod sursa(job #3219038)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 29 martie 2024 19:57:55
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define ll long long
//#define int long long
using namespace std;

const string TASK("abc2");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout

const int N = 2009, P = 666013, M = 1e9 + 123;

string s, t;
vector<ll> v;

signed main()
{
    cin >> s;

    int n = 0;
    for(ll hsh = 0; cin >> t; hsh = 0)
    {
        n = t.size();
        for(int i = 0; i < t.size(); ++i)
            hsh = (hsh * P + t[i]) % M;
        v.pb(hsh);
    }
    sort(v.begin(), v.end());

    ll pt = 1, hsh = 0;
    for(int i = 1; i <= n; ++i)pt = (pt * P) % M;

    int ans = 0;
    for(int i = 0; i < s.size(); ++i)
    {
        hsh = (hsh * P + s[i]) % M;
        if(i >= n)hsh = (hsh - (s[i - n] * pt) % M + M) % M;

        if(i + 1 < n)continue;

        auto it = lower_bound(v.begin(), v.end(), hsh);
        if(it != v.end() && *it == hsh)ans ++;
    }

    cout << ans << '\n';
    return 0;
}