Cod sursa(job #100784)

Utilizator scapryConstantin Berzan scapry Data 12 noiembrie 2007 18:46:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 2.54 kb
#include <cstdio>
#include <cstring>
#include <cassert>

enum { maxlen = 10000002, maxwordlen = 20 };
const int pow3[6] = { 1, 3, 9, 27, 81, 243 };

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

int news;

struct item
{
	item *t[243];

	item()
	{
		memset(t, 0, sizeof(t));
	}
} root;

#define printf(...) ;

inline int translate_p(const char *s)
{
	int ret = 0;

	assert(*s);
	ret *= 3;
	if(*s)
	{
		assert(*s == 'a' || *s == 'b' || *s == 'c');
		ret += (*s - 'a');
		s++;
	}

	ret *= 3;
	if(*s)
	{
		assert(*s == 'a' || *s == 'b' || *s == 'c');
		ret += (*s - 'a');
		s++;
	}

	ret *= 3;
	if(*s)
	{
		assert(*s == 'a' || *s == 'b' || *s == 'c');
		ret += (*s - 'a');
		s++;
	}

	ret *= 3;
	if(*s)
	{
		assert(*s == 'a' || *s == 'b' || *s == 'c');
		ret += (*s - 'a');
		s++;
	}

	ret *= 3;
	if(*s)
	{
		assert(*s == 'a' || *s == 'b' || *s == 'c');
		ret += (*s - 'a');
		s++;
	}

	return ret;
}

int translate(const char *s)
{
	int ret = translate_p(s);

	printf("translated [%.5s] into %d\n", s, ret);

	return ret;
}

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

	while(true)
	{
		printf("add [%.22s] at %p\n", s, pos);

		type = translate(s);
		p = &(pos->t[type]);

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

		pos = *p;

		s++;
		if(*s == 0)
			break;

		s++;
		if(*s == 0)
			break;

		s++;
		if(*s == 0)
			break;

		s++;
		if(*s == 0)
			break;

		s++;
		if(*s == 0)
			break;
	}
}

void search(const item *pos, const char *s)
{
	int i, type;

	for(i = 0; pos != 0 && i + 4 < wordlen; i += 5)
	{
		printf("%d) searching for [%.22s] at %p\n", i, s, pos);

		type = translate(s);
		pos = pos->t[type];
		s += 2;
	}

	if(pos)
	{
		printf("special) searching for [%.22s] at %p\n", s, pos);

		printf("i %d wordlen %d -> left len %d\n", i, wordlen, wordlen - i);

		type = translate(s);
		type /= pow3[5 - (wordlen - i)];
		type *= pow3[5 - (wordlen - i)];
		printf("resulting type %d\n", type);

		pos = pos->t[type];
	}

	if(pos)
	{
		printf("found!\n");
		ans++;
	}
	else
		printf("not found\n");
}

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

#undef printf

	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;
}