Cod sursa(job #2555566)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 24 februarie 2020 09:51:27
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <string>
#include <bitset>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>

using namespace std;

typedef unsigned int uint;

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

int n, m;

const uint c1 = 666013;
const uint alp = 3;
uint rm;

vector<uint> ve[c1];
struct roller{
	uint val = 0;
	void extend(char a){
		val = (val*alp)+cv(a);
	}
	void roll(char a, char b){
		val = (val - rm*cv(a))*alp + cv(b);
	}
};

bool chek(uint val){
	const vector<uint> &v = ve[val%c1];
	for(auto a : v){
		if(a == val){
			return true;
		}
	}
	return false;
}

inline void setz(uint val){
	if(!chek(val)){
		ve[val%c1].push_back(val);
	}
}

FILE *fin, *fout;
char s[10000041], q[41];

void altoire(){
	uint val = 0;
	for(int i = 0; i < n; ++i){
		val *= alp;
		val += cv(q[i]);
	}
	setz(val);
}

int sol = 0;
void rezolvescu(){
	roller r;
	for(int i = 0; i < n; ++i){
		r.extend(s[i]);
	}
	if(chek(r.val)){
		sol++;
	}
	for(int i = n; i < m; ++i){
		r.roll(s[i-n], s[i]);
		if(chek(r.val)){
			sol++;
		}
	}
	printf("%d", sol);
}

int main(){
	fin = freopen("abc2.in", "r", stdin);
	fout = freopen("abc2.out", "w", stdout);
	fgets(s, 10000041, fin);
	m = strlen(s);
	if(s[m-1] == '\n'){
		m--;
	}
	while(fgets(q, 41, fin)){
		if(n==0){
			n = strlen(q);
			if(q[n-1] == '\n'){
				n--;
			}
		}
		altoire();
	}
	rm = pow(alp, n-1);
	rezolvescu();
	return 0;
}