Task

Given a list of numbers $X$ produce a second list of numbers $Y$ such that $Y_i$ is the length of the longest common prefix of $X$ and $X$ with the first $i$ elements removed.

For example if the input is

[1,2,2,1,1,2,1,2,2,1,2,1]

The output should be

[12,0,0,1,2,0,4,0,0,2,0,1]

• The first value is 12 since the longest common prefix of the list with itself is the entire list, which is 12 long.
• The second value of the output is 0, since the second value of the input is 2 and the input does not start with 2.
• The third is also 0 for the same reason.
• The fourth value of the output is 1, since the fourth value of the input is 1 and the input starts with 1. However the fifth value of the input is 1 and the second value of the input is 2, these aren't equal so the fourth output can't be greater than 1.
• The fifth value of the output is 2, since from the fifth value on is 1,2,1 which matches the first two values of the entire input, 1,2,2.

Scoring

This is code golf so the goal is to minimize the size of your source code as measured in bytes.

I would also like you to include the "Big-O" notation of your algorithm in your answer. There are faster and slower ways to solve the above problem. Scoring should be separated into categories by language and speed, so a fast answer in Kotlin is not competing with a slow answer in Kotlin, just like a slow answer in Python is not competing with a slow answer in C.

Test cases

[1,2,3,4,5] -> [5,0,0,0,0]
[1,1,1,1,1] -> [5,4,3,2,1]
[1,1,1,2,2] -> [5,2,1,0,0]
[1,2,1,2,1] -> [5,0,3,0,1]
[1,2,2,1,2] -> [5,0,0,2,0]
[1,1,1,2,1,1,1,1,2,2] -> [10,2,1,0,3,4,2,1,0,0]
[2,3,1,1,2,3,3,2,3,1] -> [10,0,0,0,2,0,0,3,0,0]
[1,2,9,2,2,1,2,1,3,2] -> [10,0,0,0,0,2,0,1,0,0]
[1,2,9,1,2,1,2,2,1,2] -> [10,0,0,2,0,2,0,0,2,0] 
[1,2,3,1,2,3,1,2,3,1,2,3] -> [12,0,0,9,0,0,6,0,0,3,0,0]
[1,2,2,1,1,2,1,2,2,1,2,1] -> [12,0,0,1,2,0,4,0,0,2,0,1]

posted over 2 years ago

CC BY-SA 4.0

2y ago

WheatWizard‭

525 reputation 18 6 50 39