10975 - Dueue's Quiz

[misof]

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]

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]

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]

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]

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

[Moha]

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]

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]

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

thanks in advance

[brianfry713]

What is the O() runtime for your code? Describe your algorithm.

printf is faster than cout. C style char[] are faster than C++ strings.

[chylek]

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:
-read dictionary
-create Trie and fail connections on it (algorithms from web)
-read the query
-tranform the table of words into one big string, with '{' as marker which is the next character after 'z' in ASCII (preallocated memory -no reallocations)
-search words in both directions on the big string using Aho-Corasick (algorithm from web)
-output the answer.

The accepted code which I have (it's not mine) works in the same way but:
-reading words in every direction instead of creating this big string
-works on char[] (but containers are with string)
-uses map (!)

My IT teacher also doesn't know what's wrong with my code