Comments on Calculate the Z-array
Parent
Calculate the Z-array
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,1which 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]
Post
JavaScript (Node.js), 86 bytes
X=>{Y=[];for(i in X)Y[i]=0,X.slice(i).map((a,b)=>a-X[b]?i='':Y[i]++);return Y.slice``}
Using fancy notation, the time complexity is $$\sum^n_{i=1}i$$
...or $O(n^2)$, which according to this is horrible/worst haha.
Definitely can be optimized, but good enough for my standards 🙂
0 comment threads