Cod sursa(job #2473456)

Utilizator 0738076326Simon Wil 0738076326 Data 13 octombrie 2019 17:06:45
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("abc2.in");
ofstream g("abc2.out");

const int NMAX = 9871;
string s,st;
vector <int> v[NMAX + 2];

bool is(long long x){
    int i = x % NMAX;
    for(int j = 0 ; j < v[i].size() ; j++)
        if(v[i][j] == x)
            return 1;
    return 0;
}

void add(long long x){
    int i = x % NMAX;
    v[i].push_back(x);
}

int main(){
    long long i,x,y,ans = 0,j;
    f >> s;
    while(f >> st){
        x = 0;
        y = 1;
        for(i = 0 ; i < st.size() ; i++){
            x += (st[i] - 'a' + 1) * y;
            y *= 3;
        }
        if(!is(x))
            add(x);
    }
    if(st.size() > s.size()){
        g << 0;
        return 0;
    }

    if(s.size() == 1){
        if(is(s[0] - 'a' + 1))
            g << 1;
        else
            g << 0;
        return 0;
    }

    x = 0 ; y = 1;
    for(i = 0 ; i < st.size() ; i++){
        x += (s[i] - 'a' + 1) * y;
        y *= 3;
    }

    if(is(x))
        ans++;

    y /= 3;
    for(i = st.size() ; i < s.size() ; i++){
        x -= (s[i - st.size()] - 'a' + 1);
        x /= 3;
        x += y * (s[i] - 'a' + 1);
        if(is(x))
            ans++;
    }
    g << ans;

    return 0;
}