10679 - I Love Strings!!

[little joey]

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]

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]

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]

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]

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.

[CodeMaker]

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?

[Sedefcho]

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.

[Sedefcho]

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.

[Sedefcho]

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

[CrazyTerabyte]

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.

[..]

It is already said in the thread
http://online-judge.uva.es/board/viewto ... c&start=17

[hectorUCI]

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

[Gigi's Baby]

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.

[Jemerson]

#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

[nibbler]

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