### Communities

tag:snake search within a tag
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
created:<1w created < 1 week ago
post_type:xxxx type of post
Challenges

# Calculate the Z-array

+4
−0

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]

Why does this post require moderator attention?
Why should this post be closed?

+1
−0

# 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}


Attempt This Online!

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 🙂

Why does this post require moderator attention?