Pagini recente » Cod sursa (job #2639747) | Cod sursa (job #1715018) | Cod sursa (job #2345466) | Cod sursa (job #232155) | Cod sursa (job #100784)
Cod sursa(job #100784)
#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;
}