11019 - Matrix Matcher

david · Post by **david** » Mon Mar 20, 2006 2:40 pm

What, exactly, is a "character" for this problem?
It seems there are characters not in the 'a'-'z' or 'A'-'Z' range.

Emilio · Post by **Emilio** » Mon Mar 20, 2006 2:57 pm

What happen with this problem?
I sent my code about ten minutes ago and it's even being judge.
I searched in the submit history and only saw a TLE in this problem, and some problems were sent before mine and they even are being judge with the message: "Statistics not available - Program running".
What is happening?

[minutes later]

I have been seeing that in the old format to see your submissions my submissions in this problem appear "Delayed".
Why? What is happening?

krijger · Post by **krijger** » Mon Mar 20, 2006 8:37 pm

During the actual contest, I got accepted with a program which assumes all characters are 'a'-'z'.

By the way, the time limit is quite tight. During the contest, I got AC in about 2.5 seconds (when the time limit was 5 seconds), with a pretty highly optimized algorithm. (it runs in linear time and uses bitmasks all over the place).

Darko · Post by **Darko** » Mon Mar 20, 2006 9:09 pm

Before I went back to sleep, I just tried reading the file in - it took 2.5secs with Java, so I just gave up.

Darko

andresw1 · Post by **andresw1** » Mon Mar 20, 2006 9:17 pm

Can you give some hint for this problem? I know that this can be solved with Aho-Corasik string matching algortihms but I don't know how or if there is simplier solution (like a number of KMPs)

krijger · Post by **krijger** » Mon Mar 20, 2006 9:24 pm

I solved it with Aho-Corasik during the actual contest and I don't think a number of KMP's will be fast enough.

andresw1 · Post by **andresw1** » Mon Mar 20, 2006 10:03 pm

OK, so you build the tree, add special sign to the end of every row and run the algorithm. Then you get a matrix of lists... for every position you have a list which string starts there... what you do next? And how you do it fast:)

krijger · Post by **krijger** » Tue Mar 21, 2006 1:18 am

Well that's were I used bitmasks. The i-th row of the pattern can end at (x,y) in the matrix iff i==0 or the (i-1)-th row of the pattern can end at (x-1,y).

You can do this quickly with bitmasks: canhere=matchcurrow&((canprevrow<<1)|1). The problem is that you have 100 rows, and this won't fit in a long long => you have to split the 100 rows into 2 long longs.

andresw1 · Post by **andresw1** » Tue Mar 21, 2006 1:22 am

Very nice... what if you don't use bitmasks. Will it give TLE?

krijger · Post by **krijger** » Tue Mar 21, 2006 1:26 am

I don't know. Haven't tried that. But if there are 'worst cases' in the jury-input (something like all A) I think it will.

Cho · Post by **Cho** » Tue Mar 21, 2006 6:05 am

I compute the hash value (long long multiplications involved) of the small pattern. Then preprocess the large text such that the hash value of each X by Y 2D-substring can be computed in constant time. I didn't optimize the code (and found no much room for optimization). It runs roughly 2.5 secs too.

aminallam · Post by **aminallam** » Wed Mar 22, 2006 10:33 pm

Mr. Cho, can you give more insight for your hashing mechanism?
Thank you.

Cho · Post by **Cho** » Thu Mar 23, 2006 4:24 am

Let c[j] be the character of the shorter string, I define its hash value as:
Summation over all valid i,j: c[j] * (3 ^ (i*100+j)) mod 2^32
(x^y denotes x to the power y instead of bitwise-XOR.)

andresw1 · Post by **andresw1** » Thu Mar 23, 2006 10:04 pm

Hello,

Cho,
You have very nice idea but I have some doubts that this will give TLE. After you find the same hash as the patern you will need to do the slow compare to see if the matching is valid. For the test case that krijger mentioned (a lot of 'A's) this will give TLE. Do you do something else which I missed? Do you have AC?

david · Post by **david** » Fri Mar 24, 2006 3:15 am

Cho wrote:Let c[j] be the character of the shorter string, I define its hash value as:
Summation over all valid i,j: c[j] * (3 ^ (i*100+j)) mod 2^32
(x^y denotes x to the power y instead of bitwise-XOR.)

Are you sure you didn't mean, for example,
c[j] * (32 ^ (i*100+j)) mod 2^32 ?
The hash function you wrote will fail to return different values for such simple strings as "ab" and "da" (assuming a is coded as 0), so I can't believe you got AC doing that without later checking if the match is exact (in which case you should get TLE for cases where both the matrix and the pattern are full of a's, for instance).
I tried to use as a hash funtion the summation over all valid i, j of
c[j] * (32 ^(i * pattern width + j)) mod 1000000007,
but I got WA after 9.7s, so even if this approach can be made to work I wonder how you managed to get it accepted in about 2.5 seconds.