I can`t understend why answer is "1 2 3".

1 because {1}={2}, 2 because {3,1}={10,1}, and what is 3?

UPD. understood

Maybe in KMP:

a[0]...a[i]...a[j]...a[k]

a[0]...a[i]==a[j]...a[k] if a[0]...a[i-1]==a[j]...a[k-1] and a[i]==a[k].

a[i]==a[k] if and only if count of numbers which greather then a[i] in a[0]..a[i-1] is equal to count of numbers which greather then a[k] in a[j]..a[k-1].

We can use the struct like segment tree, which help us get this count in O(log(400000)) (just +1 to a[i] when we add number a[i] ans -1 else). If we get suffix(a[j]..a[k-1]) we don't forget to decrease all values which don't include to this suffix (it's a[j]..a[h], if a[j]..a[k-1]=a[j]..a[h]a[h+1]..a[k-1]). And first we should decrease all numbers as it possibly in any sequence because numbers are in the range 1..2^32 (then we can use a segment tree).

I don't know is it correct solution, but maybe.

read the solution to ceoi 2011 Matching

Since the original problem is solved using KMP, and now we have multiple patterns, naturally we should solve this problem using the generalization of KMP to multiple strings, which is Aho–Corasick.