Yes i have looked into but it is short and not very informative, as the max-flow blog.

No actually there is given only statement and algorithm of the problem, not various problems and places where it can be used. But thanks, anyways!

I sorted the strings based on their length and used a greedy approach using trie. Can you plz tell bug in this method. Thanks in Advance.

Damn Codeforces, it became too slow towards the end

https://www.quora.com/How-do-I-solve-SPOJ-Two-Paths-problem

Yes you are right, each psycho X is murdered by the nearest psycho on his left which has a greater id Y, Unless Y is itself not murdered by another psycho Z, which will take its place , but it won't take affect the solution since in that case Y will be killed by Z before it reaches X or else Y will kill X itself.

P[n] is LPS(longest proper prefix of string that is also a suffix ending at n) (refer kmp string matching algorithm if you don't know about it)

let the string be abcabcabc here P[n] = 6 ("abcabc" is suffix ending at 9 which also a prefix of original string) check if any other i has P[i]= 6, ie a prefix of length 6 ends at i(i!=n)

if you found such i , ans is P[n] else check P[P[n]] (here P[6]=3)

if P[P[n]]=0, no other suffix other than P[n] is a prefix of original string ie no solution (eg abcdabcabcd, P[n]= 4, P[P[n]]= 0, no solution )

else a string of length P[P[n]] occurs atleast 3 times in original, once in prefix, once in suffix and once in middle at position (n-P[n]+1= 4 in ("abcabcabc")) so the ans in P[P[n]]