My first solution constructed the suffix array (in O(Nlog(N)) time) for each string independently (A, B and the union of A and B) and I got Time limit exceeded. I had to change my algorithm so that it computed everything only from the suffix array (and the LCPs) of the union of A and B. I thought that was intended, but now I see that I probably have some inefficiencies in my suffix array routines, which I will have to identify.
2 Likes
does the solution that uses hashes exist ?
Where can i read more about suffix array and LCP array? (algorithm and application)
3 Likes
Amazing tutorial…gr8t work!!!
1 Like
http://www.codechef.com/viewsolution/1966634
My solution works on all test cases i found
but still gives runtime error
please help
@anton_lunyov sir may u plzz provide me the test cases where this solution is failed CodeChef: Practical coding for everyone
thanx in advance…
I can’t seem to visualise this part
U(A) + U(B) - U(A intersection B)
Which is equal to
U(A) + U(B) - (U(A union B) - U(A) - U(B))
Isn’t U(A intersection B) supposed to be = to U(A) + U(B) - U(A union B)
9 Likes
Can someone help me with the stdin and stdout for node.js. My code is as follows
process.stdin.resume();
process.stdin.setEncoding(‘utf8’);
process.stdin.on(‘data’, function (chunk) {
var lines = chunk.toString().split(’\n’);
var stringDiff = function(a,b){
var aSet = getAllSubstring(a);
var bSet = getAllSubstring(b);
var nSet = difference(aSet, bSet);
nSet = nSet.concat(difference(bSet, aSet));
return nSet.length;
}
var difference = function(a,b){
var nSet = [];
for(var i in a){
var found = false;
for(x in b){
if(a[i] === b[x]){
found = true;
break;
}
}
if(!found){ nSet.push(a[i])};
}
return nSet;
}
var getAllSubstring = function(s){
var aSet = [];
var i = 1;
var j = 0;
while(i<=s.length&&j<s.length){
var next = s.substring(j,i);
if(aSet.indexOf(next)<0){
aSet.push(next);
}
if(i===s.length){
j++;
i = j+1;
}else{
i++;
}
}
return aSet;
}
var diff = stringDiff(lines[0], lines[1]);
process.stdout.write(diff+'\n');
process.exit();
});
hello,
could you just tell me weather my code’s output is correct or not, irrespective of time exceed error…
why doesnt work?
module Main where
import Data.List
import System.Exit
al1 xs = nub . concat . map (drop 1 . inits) . tails $ xs
cmp xs xz = [ x | x <- ((al1 xs)++(al1 xz)), notElem x (intersect (al1 xs) (al1 xz) )]
main = do
line <- getLine
line2 <- getLine
putStr $ show $ length $ cmp line line2
exitWith ExitSuccessThis is my code in python. it works fine on my system but dont know why it is not working in codechef
getting run time error NZEC. first submission in codechef. so dont know much abt online compilers. plz help me out sir CodeChef: Practical coding for everyone
Wow… that was a quite a sleek approach… Nice one
This problem really showed our “level” 
1 Like
I did the same thing as the tester . My solutions (during the contest[CodeChef: Practical coding for everyone]) and after the contest with some optimizations (CodeChef: Practical coding for everyone) both TLE … Is this too strict for Java ?
EDIT: I think he has a better Suffix array function.
My O(n*(logn)*(logn)) passes !
Yes @acmonster construct LCP array using hashes in O(N log^2 N) time. We can compare two suffixes in O(log N) time using hashes. So we can sort them in O(N log^2 N) time. And then calculate LCP array in O(N log N) time.
A very good pdf on suffix arrays for contest can be found here (http://www.stanford.edu/class/cs97si/suffix-array.pdf)
Another source is MAXimal :: algo :: Суффиксный массив but make sure you open it in Chrome.
1 Like