SECPASS - Editorial

editorial
, , ,
21

Why my correct O(N) solution times out?
Please help.
Link:- https://www.codechef.com/viewsolution/23143675

22

True @shoom…

23

Sad, I got TLE for Hashing+Binary Search :frowning:

24

Test cases are very week:

O(n^2): submission,

O(n): submission

Worst case for O(n^2) solution is when all chars are same. :stuck_out_tongue:

25

I have studied ‘Z’-Algorithm from various sources . But to best of my knowledge Z function is O(m+n) algorithm
so how can we solve the problem in less than O(n^2) time . Can someone elaborate Correct logic using Z Algorithm

26

By using KMP, you can do it in O(|S|) by counting the number of times each prefix occurs in the string.
Here is the link to my code - https://www.codechef.com/viewsolution/23145983
Here is the link to the explanation - https://cp-algorithms.com/string/prefix-function.html.

27

if first two characters of a string are same, will the answer be first character always???

28

Can someone provide c++ code for the logic in the editorial?

29

Seems true wow.

30

Help needed
I have solved this problem using LSP like in KMP matching algorithm but not able to pass all the test case. Below is the link of my code. Please help me.

31

We can prove that according to the
fact, that our segments built by
moving our pointers cannot ever
intersect. If 2 of them intersecting,
it means that at least one of our
pointers point to some index with
corresponding letter equal to the
string’s first letter. BUT when we
started a substring from the last
appearance of our string’s first
letter, there’s no other appearance in
front of it, so it’s guaranteed that
there will be a mismatch (or it
reached the end of the string).

I didn’t understand this. Can somebody please explain.

32

I understand the solution now, well also, what is the use of k here? and what is exactly k? isnt ans is k?

33

Basically there is no point to consider prefixes where the first letter appears more than once. Such prefix occurs fewer times that a single-letter prefix, so it can’t be a candidate for the answer.
For example the prefix ‘abca’ appears fewer times than the prefix ‘a’.

34

In Z algo you create a Z array where each index stores the largest substring starting at i and is also a prefix
Now cosider the string “abcabcabc”
Here the z array looks like this : 0 0 0 6 0 0 3 0 0
In the above array 6 denotes the substring “abcabc” which is also the prefix and 3 denotes the substring “abc” which is also the prefix
Now if you look carefully, in the substring you “abcabc” you are getting one time occurence of the prefixes : “a”, “ab”, “abc”,“abca”,“abcab”,“abcabc”. Similarly in the case of “abc”.

35

So you can keep an array where each index i denotes the occurence of the prefix of length i. So for each non-zero element(say z[i]) in the z-array you update all the elements between the range 1 to z[i] of the frequency array index by adding 1 to them. This will give you an array containing the frequency of all the prefixes. Then you check for the element with largest frequency and for a tie, check for the largest element

36

This is my solution in pypy3 : https://www.codechef.com/viewsolution/23144894

37

let our string be abcdeabcf. On first scan, our k is a as our answer is currently a. Then on 2nd scan, k becomes 2 as answer becomes 2 and later on k becomes 3 when answer is 3. So K is length of our answer at any instance.

38

Here it is…
https://www.codechef.com/viewsolution/23190005

39

This was a good problem for Z algorithm and KMP