Cod sursa(job #2555474)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 24 februarie 2020 08:53:04
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <string>
#include <bitset>
#include <vector>

using namespace std;

typedef long long lint;

lint cv(char c){
	return c-'a';
}

int blog2(int a){
	int r = 1;
	while(a>0){
		a >>= 1;
		r <<= 1;
	}
	return r;
}

const lint c1 = 50441;

vector<lint> ve[c1];
struct roller{
	const lint alp = 3;
	lint val = 0, rm = 1;
	int mv;
	void extend(char a){
		val = (val*alp)+cv(a);
		rm *= alp;
		mv = (val%c1);
	}
	void extend(const string &s){
		for(auto c : s){
			extend(c);
		}
	}
	void roll(char a, char b){
		val = (val*alp) - rm*cv(a) + cv(b);
		mv = (val%c1);
	}
	int bser(){
		const vector<lint> &v = ve[mv];
		if(v.empty()){
			return 0;
		}
		int ps = -1;
		for(int i = blog2(v.size())<<1; i > 0; i >>= 1){
			if(ps+i < v.size() && val < v[ps+i]){
				ps += i;
			}
		}
		return ps+1;
	}
	bool chek(){
		if(ve[mv].empty()){
			return false;
		}
		int ps = bser();
		return ve[mv][ps]==val;
	}
	void setz(){
		vector<lint> &v = ve[mv];
		int ps = bser();
		if(ps == v.size()){
			v.push_back(val);
		}else{
			if(v[ps] != val){
				v.insert(v.begin()+ps+1, val);
			}
		}
	}
};

ifstream fin("abc2.in");
ofstream fout("abc2.out");

string s, q;
void altoire(const string &a){
	roller r;
	r.extend(a);
	r.setz();
}

int n;
int sol = 0;
void rezolvescu(){
	roller r;
	for(int i = 0; i < n; ++i){
		r.extend(s[i]);
	}
	if(r.chek()){
		sol++;
	}
	for(int i = n; i < s.size(); ++i){
		r.roll(s[i-n], s[i]);
		if(r.chek()){
			sol++;
		}
	}
	fout << sol;
}

int main(){
	// ios_base::sync_with_stdio(false);
	fin >> s;
	while(fin >> q){
		n = q.size();
		altoire(q);
	}
	rezolvescu();
	return 0;
}