Cod sursa(job #2473722)

Utilizator 0738076326Simon Wil 0738076326 Data 14 octombrie 2019 09:37:28
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

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

typedef unsigned int ii;
const int NMAX = 7001;
string s,st;
vector <ii> v[NMAX + 2];
ii put[30],n,m,pos;

bool is(ii x){
    for(ii it: v[pos])
        if(it == x)
            return 1;
    return 0;
}

void add(ii x){
    v[pos].push_back(x);
}

int main(){
    ii i,x,y,ans = 0,j;
    f >> s;
    f >> st;
    n = st.size();
    m = s.size();
    put[0] = 1;
    for(i = 1 ; i <= n ; i++)
        put[i] = put[i - 1] * 3;

    x = 0;
    for(i = 0 ; i < n ; i++){
        x += (st[i] - 'a') * put[i];
    }
    pos = x % NMAX;
    if(!is(x))
        add(x);

    while(f >> st){
        x = 0;
        for(i = 0 ; i < n ; i++){
            x += (st[i] - 'a') * put[i];
        }
        pos = x % NMAX;
        if(!is(x))
            add(x);
    }

    x = 0 ;
    for(i = 0 ; i < n ; i++){
        x += (s[i] - 'a') * put[i];
    }

    pos = x % NMAX;
    if(is(x))
        ans++;

    for(i = n ; i < m ; i++){
        x -= (s[i - n] - 'a');
        x /= 3;
        x += put[n - 1] * (s[i] - 'a');
        pos = x % NMAX;
        if(is(x))
            ans++;
    }

    g << ans;
    return 0;
}