Cod sursa(job #2288542)

Utilizator flibiaVisanu Cristian flibia Data 23 noiembrie 2018 16:51:25
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>
#pragma GCC optimize("03")

using namespace std;

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

struct nod {
	int nrcuv;
	nod *son[3];
	nod () {
		nrcuv = 0;
		memset(son, 0, sizeof son);
	}
};

string s, g;
nod *root = new nod();

void baga(nod *T, int p, int sz) {
	if (p == sz) {
		T -> nrcuv++;
		return;
	}
	if (T -> son[g[p] - 'a'] == NULL)
		T -> son[g[p] - 'a'] = new nod();
	baga(T -> son[g[p] - 'a'], p + 1, sz);
}

int chk(nod *T, int p, int sz) {
	if (T -> nrcuv > 0)
		return 1;
	if (p == sz || T -> son[s[p] - 'a'] == NULL)
		return 0;
	return chk(T -> son[s[p] - 'a'], p + 1, sz);
}

int main() {
	in >> s;
	while (in >> g) {
		int sz = g.size();
		baga(root, 0, sz);
	}
	int sz = s.size(), rs = 0;
	for (int i = 0; i < sz; i++) 
		rs += chk(root, i, min(sz, i + 20));
	out << rs;
	return 0;
}