Cod sursa(job #98162)

Utilizator scapryConstantin Berzan scapry Data 10 noiembrie 2007 10:35:28
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.39 kb
#include <cstdio>
#include <cstring>
#include <cassert>

enum { maxlen = 10000002, maxwordlen = 20 };

int wordlen;
int len;
char str[maxlen];
int ans;

int news;

struct item
{
	item *a, *b, *c;

	item() : a(0), b(0), c(0)
	{
	}
} root;

void add(item *pos, const char *s)
{
	item **p;

	while(*s)
	{
		//printf("add [%s] at %p\n", s, pos);

		p = 0;
		switch(*s)
		{
			case 'a': p = &(pos->a); break;
			case 'b': p = &(pos->b); break;
			case 'c': p = &(pos->c); break;
		}
		assert(p);

		if(*p == 0)
		{
			*p = new item;
			news++;
		}

		pos = *p;
		s++;
	}
}

void search(const item *pos, const char *s)
{
	for(int i = 0; i < wordlen; i++)
	{
		//printf("%d) searching for [%s] at %p\n", i, s, pos);

		if(!pos)
		{
			//printf("not found\n");
			return;
		}

		switch(*s)
		{
			case 'a': pos = pos->a; break;
			case 'b': pos = pos->b; break;
			case 'c': pos = pos->c; break;
		}

		s++;
	}

	//printf("found!\n");
	ans++;
}

void go()
{
	for(char *start = str + len - wordlen; start >= str; start--)
	{
		search(&root, start);
		//printf("\n");
	}

	printf("ans eventually %d\n", ans);
}

int main()
{
	char word[maxwordlen + 2];

	freopen("abc2.in", "r", stdin);
	scanf("%s", str);
	len = strlen(str);
	while(scanf(" %s", word) != EOF)
	{
		add(&root, word);
		//printf("\n");
	}
	wordlen = strlen(word);

	printf("%d news\n", news);

	go();
	
	freopen("abc2.out", "w", stdout);
	printf("%d\n", ans);
	return 0;
}