10679 - I Love Strings!!

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Aug 12, 2004 9:19 am

It might be a matter of taste, but in my opinion the empty string is a substring of any other string. But in this problem you're supposed to reply 'n' to an empty query. And there are empty queries in the input. IMO this fact should be mentioned in the problem description since it deviates from what is commonly accepted. Correct me if I'm wrong.

[EDIT] Sorry there are no empty queries. I mis-interpreted a query starting with an illegal character as an empty string. How could I be so stupid...[/EDIT]

To the problemsetter, who is so eager to change the ranges and input for this problem as soon as people find clever ways to circumvent his special cases (but leaves the illegal characters in the input file): My algorithm is quite simple and needs no advanced data structures like prefix trees, only a few arrays, and is reasonably fast on average. Its worst case behaviour is still O(n*m) though, but it will be quite difficult to devise the special case that gives me TLE.

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

Post by dpitts » Tue Sep 21, 2004 9:37 pm

Well, the algorithm I used is rather simple. I just construct a DFA tree for all "test" cases, and run the input through it. I still get .600 seconds though. Twice as long as the next person. Any idea's on how to speed it up (Not that it REALLY matters).

I wonder if my time is being used more in the DFA construction or the search itself.

I read the entire file in at once, and write my output all at once, so know thats not the bottleneck.

Oh well, speeds not THAT important. It probably has to do with my use of linked lists, or at least dynamic memory. Whats the overhead of malloc, and is there a faster alternative? I don't bother freeing anything, since I really don't need to in this case.

Kuba12
New poster
Posts: 9
Joined: Sat Jan 11, 2003 1:51 pm

Post by Kuba12 » Sun Oct 24, 2004 3:27 pm

I just got AC for this problem with an incorrect program. It turned out that there aren't any queries which are suffixes of other queries. For example, for the following input:
1
abcde
2
abcd
bcd
my accepted program outputs:
y
n

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Fri Dec 31, 2004 3:19 pm

I am using getchar() to read input strings and still getting TLE, which appears
to me to be due to incorrect input processing only.Can someone help me with some inputs/output?

Regards,
Suman.

CrazyTerabyte
New poster
Posts: 25
Joined: Fri Jul 16, 2004 3:19 am
Location: Brazil
Contact:

Post by CrazyTerabyte » Fri Dec 31, 2004 4:40 pm

sumankar wrote:I am using getchar() to read input strings and still getting TLE, ...
getchar is slowest of all methods. You should read a "block" (or a line) per time. It will be much faster.

IOW, use fgets or scanf.

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sat Jan 01, 2005 6:33 am

Can this problem be solved by KMP algo now? I got Acc during the contest and after rejudge my code got TLE and I didn't try to fix it till now, but one of my friends told me that he got TLE using KMP...so I am a bit confused.

Do I have to find some tricky way or is it possible to get Acc using the tipical KMP algo? :-?
Jalal : AIUB SPARKS

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Algorithms on 10679

Post by Sedefcho » Sat Feb 12, 2005 12:43 am

Yes, I have the same question. Does it work with
Knutt-Moris-Prat algorithm ?

To my opinion - no, it doesn't work. I get TLE.

My program is written in C++ ( of course that's not of
a big importance but ... ) .

So can someone summarize the algorithms using which we
can pass the time limit.
And give some Internet links please about them.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sat Feb 12, 2005 12:46 am

By the way I use gets(line) so I read line per line.

So if what CrazyTerabyte says is true ( that reading line by line
is much faster than getchar ) than I can claim I have no
inefficient parts in my C++ program.

I am not a C++ expert that is why I tend to
believe CrazyTerabyte.

But the KPM algorithm is implemented in 99% the best possible way.
I see no optimizations I can make.

Thank you in advance.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sat Feb 12, 2005 12:47 am

I meant
But the KMP algorithm is implemented in 99% the best possible way.
I see no optimizations I can make.

CrazyTerabyte
New poster
Posts: 25
Joined: Fri Jul 16, 2004 3:19 am
Location: Brazil
Contact:

Post by CrazyTerabyte » Sat Feb 12, 2005 3:45 am

I never tried this problem, but I know that some very time-tight problems may result in a time-limit with C++ "cin" and "cout" (just because the overhead needed for objects).

I don't know if it happes with this problem, but I know (from what I've read in this thread) that many people got accepted during contest-time, and time limit after that. Maybe even the KMP algorithm isn't enough for testcases of this problem. I really don't know.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Feb 12, 2005 5:42 am

My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

hectorUCI
New poster
Posts: 4
Joined: Tue Mar 01, 2005 8:36 am

10679 Please review

Post by hectorUCI » Tue Mar 01, 2005 8:42 am

I think this solution work but I received WRONG ANSWER. I would like anybody review this code in order to get the bugs because I can

User avatar
Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

Post by Gigi's Baby » Mon May 02, 2005 4:33 am

I think this problem can be solved by using suffix tree or suffix array.
But my code of suffix tree got Memory Limit Exceeded,
another code of suffix array got Time Limit Exceeded. :(

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson » Thu May 12, 2005 9:46 pm

#JAVA CODE

Code: Select all

    public static int BMmatch (String text, String pattern) {
        int [] last = buildLastFunction(pattern);
        int n = text.length();
        int m = pattern.length();
        int i = m-1;
        if (i > n - 1)
            return -1;   
        int j = m - 1;
        do {
	        if (pattern.charAt(j) == text.charAt(i)) {
		        if (j == 0) {
		            return i; 
		        } else { 
			          i--; 
			          j--;
		        }
	        } else {
	            i = i + m - Math.min(j, 1+ last[text.charAt(i)]);
	            j = m - 1;
	        }
        } while (i <= n - 1);
        return -1;
    }
    
    
    public static int[] buildLastFunction (String pattern) {
        int [] last = new int[128];
        for (int i = 0; i < 128; i++) 
            last[i] = -1;
        for(int i = 0; i < pattern.length(); i++) 
            last[pattern.charAt(i)] = i; 
        return last;
    }  
This is my Boyler-Moore algo, but I keep on TLE, could someone please tell me what the heck is wrong with it?

Thanx in advance
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

nibbler
New poster
Posts: 22
Joined: Fri Jun 04, 2004 10:30 pm

Post by nibbler » Tue May 31, 2005 11:05 am

This is not Boyer-Moore, this is Quick search algorithm
http://www-igm.univ-mlv.fr/~lecroq/stri ... CTION00190
Notice the O(n*m) running time

Post Reply

Return to “Volume 106 (10600-10699)”