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
stanford link is not working!!!
In the stanford link ‘)’ is part of the hyperlink pasted here . Remove that and paste the link in your browser and you will able to access the pdf .
Or use this link : http://www.stanford.edu/class/cs97si/suffix-array.pdf
1 Like
Try large test where both strings have equal characters.
The first test in the system has the form
string(99990,‘x’)
string(99969,‘x’)
and the answer obviously is 21,
while your answer is 25769803797.
3 Likes
thank you sir…
accepted…
my nlogn passed
oops there was a silly mistake, got AC learnt a lot from this question
works fine here runs but (time exceed)
import List
Import System
Might be that we need to find U(A) + U(B) - 2*U(A intersection B) because common substrings appear twice.
Probably you misunderstand the idea of contest programming - your code have to return correct answer for each available input, not only the one in problem statement and your program return 8 for each input, simply because you are NOT reading input from stdin…
If U(a) is taken to represent the set of all unique substrings of a, and |U(a)| its size, then the final expression should be: 2*|U(a) UNION U(b)| - |U(a)| - |U(b)|
1 Like
First try to comment System.exit(0); - killing JVM is not a good idea in general…
I’d say, that problem is with memory, you want to allocate array of strings of length n^2 (and n is 100000).
array of strings with no of strings is n2, where n2 being 10 for a four letter word
10=4+3+2+1
so n2=no of letters +(no of letters-1)+…+ 1
and sir system.exit(0) presence or absence has no effect in this case in the runtime error…
any other suggestions sir ?
thanks