Cod sursa(job #614922)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 8 octombrie 2011 00:50:13
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAXN 10000010

struct nod {
	nod *fii[4];
};

long i, len, QUE, sol, j;
char s[MAXN], sir[25];

nod *p, *trie, *trie2, *que[1000010], *back, *aux;

int main() {
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);
	
	scanf("%s", s);
	p = new nod;
	for (i = 0; i < 4; ++i) p->fii[i] = NULL;
	
	while (scanf("%s", sir) == 1) {
		
		fprintf(stderr, "%s\n", sir);
		
		len = strlen(sir);
		trie = p;
		
		for (i = 0; i < len; ++i) {
			
			if (trie->fii[sir[i] - 'a'] == NULL) {
				fprintf(stderr, "Aloc %d\n", i);
				trie->fii[sir[i] - 'a'] = new nod;
				for (j = 0; j < 4; ++j) trie->fii[sir[i] - 'a']->fii[j] = NULL;				
				
				trie = trie->fii[sir[i] - 'a'];
			} else {
				trie = trie->fii[sir[i] - 'a'];
			}
			
		}
		
	}
	
	for (i = 0; i < 3; ++i) {
		if (p->fii[i] != NULL) {
			p->fii[i]->fii[3] = p;
			que[++QUE] = p->fii[i];
		}
	}
	
	for (i = 1; i <= QUE; ++i) {
		
		trie2 = que[i];
		back = trie2->fii[3];
		aux = back;
		
		for (j = 0; j < 3; ++j) {
			back = aux;
			
			if (trie2->fii[j] != NULL) {
				while (back->fii[j] == NULL && back != p) {
					back = back->fii[3];
				}
				
				if (back->fii[j] != NULL) {
					trie2->fii[j]->fii[3] = back->fii[j];				
				} else {
					trie2->fii[j]->fii[3] = back;
				}
				
				que[++QUE] = trie2->fii[j];				
			}
		}
	}
	
	len = strlen(s);
	for (i = 0; i < len; ++i) {
		
		while (p->fii[s[i] - 'a'] == NULL && p->fii[3] != NULL) {
			p = p->fii[3];
		}
		
		if (p->fii[s[i] - 'a'] != NULL) {
			p = p->fii[s[i] - 'a'];
		}
		
		long ok = 0;
		for (j = 0; j < 3; ++j) {
			if (p->fii[j] != NULL) {
				ok = 1;
				break;
			}
		}
		
		if (ok == 0) {
			++sol;
		}
		
	}
	
	printf("%ld\n", sol);
	
	return 0;
}