Cod sursa(job #2288552)

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

using namespace std;

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

char s[10000010], g[22];
nod *root = new nod();

void baga(nod *T, char *g, 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'], g, p + 1, sz);
}

int chk(nod *T, char *s, 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'], s, p + 1, sz);
}

int main() {
	FILE* in = freopen("abc2.in", "r", stdin);
	FILE* out = freopen("abc2.out", "w", stdout);
	fscanf(in, "%s", s);
	while (fscanf(in, "%s", g) == 1) {
		int sz = strlen(g);
		baga(root, g, 0, sz);
	}
	int sz = strlen(s), rs = 0;
	for (int i = 0; i < sz; i++) 
		rs += chk(root, s, i, min(sz, i + 20));
	cout << rs;
	return 0;
}