String

Question 1

Z algorithm - time and space complexity (prefix and string matching)

Answer 1

String matching:
Time: O(n+m)
Space: O(n+m)
Where n is the length of the pattern and m is the length of the text

Prefix:
Time: O(n)
Space: O(n)
Where n is the length of the string

Question 2

Z algorithm (string matching) - how does it works

Answer 2

1) combine text and pattern with a special character (eg $&@“) which does not exist in both string
2) create z array with the algorithm
How does the algorithm form the z array: google of you forget
3) count the number of x(length of the pattern) in the array
4) that’s the answer

Question 3

Z algorithm (prefix matching) - what it’s going to do

Answer 3

Find substring which is also the prefix of the original string

Question 4

Manacher’s algorithm (longest palindromic substring)

- time and space complexity

Answer 4

Time: O(n) - linear
Space: O(n)
Where n is the length of the given string