Compress Words
Contest: Codeforces Round 578 (Div. 2)
Difficulty rating: 2000
Tags: brute force, hashing, implementation, string suffix structures, strings

Amugae has a sentence consisting of $$$n$$$ words. He want to compress this sentence into one word. Amugae doesn't like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges "sample" and "please" into "samplease".

Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of the words in Amugae's sentence.

The second line contains $$$n$$$ words separated by single space. Each words is non-empty and consists of uppercase and lowercase English letters and digits ('A', 'B', ..., 'Z', 'a', 'b', ..., 'z', '0', '1', ..., '9'). The total length of the words does not exceed $$$10^6$$$.

Output format:
In the only line output the compressed word after the merging process ends as described in the problem.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
5
I want to order pizza

Example output:
Iwantorderpizza

Example input:
5
sample please ease in out

Example output:
sampleaseinout

Editorial:
Denote the words from left to right as $$$W_1, W_2, W_3, \cdots, W_n$$$.
If we define string $$$F(k)$$$ as the result of merging as described in the problem $$$k$$$ times, we can get $$$F(k+1)$$$ by the following process:
1. If length of $$$F(k)$$$ > length of $$$W_{k+1}$$$   Assume the length of $$$F(K)$$$ is $$$x$$$, and the length of $$$W_{k+1}$$$ is $$$y$$$. Construct the string $$$c = W_{k+1} + F(k)[x-y...x] $$$ ( * $$$s[x..y]$$$ for string $$$s$$$ is the substring from index $$$x$$$ to $$$y$$$)  Get the KMP failure function from string $$$c$$$.  We can get maximum overlapped length of $$$W_{k+1}$$$'s prefix and $$$F(k)$$$'s suffix from this function. Suppose the last element of the failure function smaller than the length of $$$W_{k+1}$$$ is $$$z$$$. Then the longest overlapped length of $$$F(k)$$$'s suffix and $$$W_{k+1}$$$'s prefix is $$$min(z, y)$$$. Let $$$L = min(z, y)$$$.  Then, $$$F(k+1) = F(k) + W_{k+1}[L+1...y]$$$
2. Assume the length of $$$F(K)$$$ is $$$x$$$, and the length of $$$W_{k+1}$$$ is $$$y$$$. Construct the string $$$c = W_{k+1} + F(k)[x-y...x] $$$ ( * $$$s[x..y]$$$ for string $$$s$$$ is the substring from index $$$x$$$ to $$$y$$$)
3. Get the KMP failure function from string $$$c$$$.
4. We can get maximum overlapped length of $$$W_{k+1}$$$'s prefix and $$$F(k)$$$'s suffix from this function. Suppose the last element of the failure function smaller than the length of $$$W_{k+1}$$$ is $$$z$$$. Then the longest overlapped length of $$$F(k)$$$'s suffix and $$$W_{k+1}$$$'s prefix is $$$min(z, y)$$$. Let $$$L = min(z, y)$$$.
5. Then, $$$F(k+1) = F(k) + W_{k+1}[L+1...y]$$$
6. Otherwise   Construct $$$c$$$ as $$$W_{k+1}[1...x] + F(k)$$$. We can get $$$F(k+1)$$$ from the same process described in 1.
7. Construct $$$c$$$ as $$$W_{k+1}[1...x] + F(k)$$$. We can get $$$F(k+1)$$$ from the same process described in 1.
In this process, we can get $$$F(k+1)$$$ from $$$F(k)$$$ in time complexity $$$O(len(W_{k+1}))$$$. So, we can get $$$F(N)$$$ (the answer of this problem) in $$$O(len(W_1) + len(W_2) + \cdots + len(W_N))$$$.