## 10975 - Dueue's Quiz

Moderator: Board moderators

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
mf wrote:You can solve it, using a trie data structure to keep the words.
That's simpler to implement than Aho-Corasick.
In the Aho-Corasick implementation I know you build a trie from the words you search and then construct a set of "failure links". How does this differ from the solution you propose?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
In my solution I only need the trie itself. I don't have to compute failure links.
For each starting cell and for each of the eight possible directions, I traverse the trie from the root, spelling out the corresponding string of letters. If some visited vertex represent the last character of a word, I increment the counter for that word.
My solution runs in O(n^3) time per query (where n=max(N,M)).

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
mf wrote:In my solution I only need the trie itself. I don't have to compute failure links.
For each starting cell and for each of the eight possible directions, I traverse the trie from the root, spelling out the corresponding string of letters. If some visited vertex represent the last character of a word, I increment the counter for that word.
My solution runs in O(n^3) time per query (where n=max(N,M)).
Ah, OK, I thought that you meant a simpler way to achieve a time complexity comparable to Aho-Corasick

kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

### Wrong input

I believe the input file is wrong. I think there are some lines shorter than N characters.
I've tested it with this code:

Code: Select all

``````#include <cassert>
#include <cstdio>
#include <cstring>

using namespace std;

int main( void ) {
int T, D, Q, M, N;
char buff[10000];
scanf( "%d", &T );

for( int tt = 0; tt < T; ++tt ) {

scanf( "%d", &D );
for( int dd = 0; dd < D; ++dd )
scanf( "%s", buff );

scanf( "%d", &Q );
for( int qq = 0; qq < Q; ++qq ) {
scanf( "%d%d", &M, &N );
for( int mm = 0; mm < M; ++mm ) {
scanf( "%s", buff );
assert( strlen( buff ) == N );
}
}
}
return 0;
}
``````

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
well i had lots of trouble witht he input system. so those who will try this problem for them:

(here: W is string, board[][] is char and others are int)

Code: Select all

``````	cin>>cases;
for(ks=1;ks<=cases;ks++)
{
cin>>d;

for(i=1;i<=d;i++)
{
cin>>W;
if(W.size()<=100) //<---- this is important. without it u will get RTE. i dont know why!
{
}
}

cin>>Q;
for(q=1;q<=Q;q++)
{
cin>>R>>C;
for(i=0;i<R;i++)
for(j=0;j<C;j++)
cin>>board[i][j];
}
}
}``````
Self judging is the best judging!

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
The inputs are correct. Also your point is correct, because you should throw away the words bigger than 100! You should deduce it from the problem description.

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

### Re: 10975 - Dueue's Quiz

WA here... What's the correct output for this case: http://paste-it.net/raw/public/n9a7fba/
(i'm linking it because it's too big to post)

Thanks.

chylek
New poster
Posts: 7
Joined: Fri Mar 22, 2013 7:50 pm
Location: Poland

### Re: 10975 - Dueue's Quiz

Can anyone tell me why do I get TLE? On the big input from this topic my program runs faster than accepted one (times: 0.9s and 1.1s).

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <queue>

using namespace std;

int counter[15000];
string dict[15000];

struct letter
{
letter *fail,*next[27];
set<int> s;
};

void free (letter *_l)
{
for(int i=0; i<26; i++)
if(_l->next[i]!=NULL )
free(_l->next[i]);
delete[]_l;
}

int main()
{
int tests,d,queries,m,n;
char str[1001];
string s,words[100],w;
letter l,*tmp,*x;
set<int> in;
queue<letter*> q;
s.reserve(100);
for(int i=0; i<15000; i++)
dict[i].reserve(1000);
for(int i=0; i<100; i++)
words[i].reserve(100);
w.reserve(400000);
scanf("%d",&tests);
for(int t=1; t<=tests; t++)
{
l.fail=NULL;
for(int i=0; i<26; i++)
l.next[i]=NULL;
l.next[26]=&l;
l.s.clear();
printf("Test Case #%d\n",t);
scanf("%d",&d);
getchar();
for(int i=0; i<d; i++)
{
fgets(str,sizeof(str),stdin);
str[strlen(str)-1]=0;
if(strlen(str)<101)
{
dict[i]=string(str);
counter[i]=0;
}
else
{
d--;
i--;
}
}

// tworzenie drzewa Trie
for(int i=0; i<d; i++)
{
tmp=&l;
for(unsigned int j=0; j<dict[i].size(); j++)
{
if(tmp->next[dict[i][j]-97]==NULL)
{
tmp->next[dict[i][j]-97]=new letter[1];
tmp=tmp->next[dict[i][j]-97];
for(int j=0; j<26; j++)
tmp->next[j]=NULL;
tmp->next[26]=&l;
}
else
tmp=tmp->next[dict[i][j]-97];
}
tmp->s.insert(i);
}

// uzupelnianie fail przejsc (skroty na drzewie)
for(int i=0; i<26; i++)
if(l.next[i]!=NULL)
{
l.next[i]->fail=&l;
q.push(l.next[i]);
}
else
l.next[i]=&l;
while(!q.empty())
{
tmp=q.front();
q.pop();
for(int i=0; i<26; i++)
if(tmp->next[i]!=NULL)
{
q.push(tmp->next[i]);
x=tmp->fail;
while(x->next[i]==NULL)
x=x->fail;
x=x->next[i];
tmp->next[i]->fail=x;
tmp->s.insert(x->s.begin(),x->s.end());
}
}

scanf("%d",&queries);
for(int c_queries=1; c_queries<=queries; c_queries++)
{
printf("Query #%d\n",c_queries);
w="";
scanf("%d %d",&m,&n);
getchar();

// konwersja tabeli na 1 dlugi napis
for(int i=0; i<m; i++)      // wczytywanie + poziomo
{
fgets(str,sizeof(str),stdin);
str[strlen(str)-1]=0;
words[i]=string(str);
w+=words[i]+'{';
}
for(int i=0; i<n; i++)      // pionowo
{
s="";
for(int j=0; j<m; j++)
s+=words[j][i];
w+=s+'{';
}
for(int i=m-1; i>0; i--)    // na ukos \ (w pionie)
{
s="";
for(int j=0; i+j<m && j<n; j++)
s+=words[i+j][j];
w+=s+'{';
}
for(int i=0; i<n; i++)      // na ukos \ (w poziomie)
{
s="";
for(int j=0; i+j<n && j<m; j++)
s+=words[j][i+j];
w+=s+'{';
}
for(int i=m-1; i>0; i--)    // na ukos / (w pionie)
{
s="";
for(int j=0; i+j<m && j<n; j++)
s+=words[i+j][n-1-j];
w+=s+'{';
}
for(int i=n-1; i>=0; i--)   // na ukos / (w poziomie)
{
s="";
for(int j=0; i-j>=0 && j<m; j++)
s+=words[j][i-j];
w+=s+'{';
}

// wyszkiwanie wzorcow
tmp=&l;
for(unsigned int i=0; i<w.size(); i++)
{
n=w[i]-97;
while(tmp->next[n]==NULL)
tmp=tmp->fail;
tmp=tmp->next[n];
for(set<int>::iterator it=tmp->s.begin(); it!=tmp->s.end(); it++)
{
counter[*it]++;
in.insert(*it);
}
}
tmp=&l;
for(int i=w.size()-1; i>=0; i--)
{
n=w[i]-97;
while(tmp->next[n]==NULL)
tmp=tmp->fail;
tmp=tmp->next[n];
for(set<int>::iterator it=tmp->s.begin(); it!=tmp->s.end(); it++)
{
counter[*it]++;
in.insert(*it);
}
}
for(set<int>::iterator it=in.begin(); it!=in.end(); it++)
//printf("%s %d\n",dict[*it].c_str(),counter[*it]);
cout<<dict[*it]<<' '<<counter[*it]<<endl;
in.clear();
}
for(int i=0; i<26; i++)
if(l.next[i]!=NULL)
{
if(l.next[i]!=&l)
free(l.next[i]);
l.next[i]=NULL;
}
printf("\n");
}
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10975 - Dueue's Quiz

printf is faster than cout. C style char[] are faster than C++ strings.
Check input and AC output for thousands of problems on uDebug!

chylek
New poster
Posts: 7
Joined: Fri Mar 22, 2013 7:50 pm
Location: Poland

### Re: 10975 - Dueue's Quiz

I don't know the O() runtime, but I'm using Aho-Corasick for serching words which should have linear complexity and reserving memory for strings (so concatenations are done without any reallocation).
I have second code with char[] and printf instead of string and cout but it gets about 15s on my computer for this big input (and also gets TLE on UVa). What's about the cout - I'm using it in only one place to print strings (on my computer string::c_str() and printf gets more time than cout).

Algorithm: