Use the cheaters as motivation to get better, if you get better than their results then in contests you'll be stealing rating out of them :)

Partial Correct Solution/Comment.

I am also Angry on Cheater(You can find my blog here ) but blaming whole indian community doesnt sounds well.

I know 85%-95% cheaters are indian. But you should also rememeber there are many good CP programmers from Indian

You must know

You have right to blame cheaters but no india

Your comment was 50% correct 50% wrong should I Downvote or Upvote Confused!

+1

I agree with you You can blog related to this hete Cheating in Snackdown

I think this non-issue will become quite a real one in the next 2 rounds. (They are 48-hour rounds which are supposed to select 3000 people.)

It was an excellent honeypot

The prefix function P of S1 + “$” + X tells you the longest prefix of S1 ending at each index of X, and also at each index of S1. Suppose you know that a prefix of length L1 ends at a certain index. Then a prefix of length P[L1-1] also ends there, and P[P[L1-1]-1], and so on. So you initially find the max L2 values (longest prefix of S2 starting after the prefix of S1) for each L1. Then you iterate from longest down to 0, and every time we process L1, we also say Ans[P[L1-1]] = max(itself, Ans[L1]). This dynamically (O(len(S1))) updates all the shorter derivatives of a prefix using the prefix function.

Commented code here

we calculate the largest prefix of s1 ending at index i of x be A(KMP), and the largest prefix of s2 starting at x be B(Z-array). Now, we take another array g, where g[i] is the largest length of any prefix of S2 with s1[0...i] as its prefix. g can be calculated by arrays A and B(g[A[i]] = max(g[A[i]], B[i + 1])), or rolling hash.

Finally we calculate KMP array pi on s1, and we iterate backward from n to 0, and ans += g[i] + 1, and g[pi[i]] = max(g[pi[i]] ,g[i]), meaning we move on the next largest prefix. The last part is a bit similar to directed graphs. Also, you have to check if a given length of prefix exists or you'll add an extra one

My solution is a bit confusing. But I will try to explain it.

Our aim is to find the maximum prefix length of s2 which follows a certain prefix length of s1. If prefix (s2) of max length 5 follows a prefix (s1) of length 3, then there will be 6 different ordered pairs for a length 3 prefix. And we have to add this for all the prefixes of s1. Let this max value I am storing in the ans[].

Do KMP for s1. Now for each prefix of s1, you will have the largest suffix ending at the same index. Create a vector<vector> prev to store the lengths of prefixes that contain a certain suffix. For example, if s1 is preabcpre, then your prefix of length 9 contains one prefix of length 3. prev[3] = {9}. Rest will be empty. One thing to note here is that ans[3] will always be greater than equal to ans[9] because the prefix of length 9 will always contain the prefix of length 3. So, we can do a DP to calculate the answers for all prefixes starting from the largest prefix to the prefix of length 0.

Form Z array of the string temp1 = s2+"#"+x. This will give the max length prefix of s2 at each index.

Do KMP for temp2 = s1+"#"+x. Now at each index just calculate the ans[] by looking at the KMP array of temp2 and z array of temp1 and then apply the DP to calculate the final ans[] and do the summation of all the elements of ans[] to get the final answer.

My code : https://ideone.com/Ble4xK

Yes

Thanks for pointing this out. It's been added now.