CLSTRN - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Subham Das
Tester: Soumik Sarkar
Editorialist: Soumik Sarkar

DIFFICULTY:

EASY

PREREQUISITES:

Stack

PROBLEM:

Find the maximum number of times string A can be extracted from string B sequentially.

EXPLANATION:

It is clear that repeatedly removing string A from B has quadratic complexity, which is not efficient enough to clear the time limit. Taking a different perspective, this is a very straightforward problem to be solved using a stack data structure.

The elements in the stack are prefixes of string A. Initially the stack is empty. As we scan each character of B, we insert the first character of A when found into this stack. If we find the second character of A next, we add to this prefix at the top of the stack. Continuing this way, if we build up the whole of string A, we can pop off the top of the stack and increment the answer counter. However if we come upon the first character of A again, we push a new prefix onto the stack and work with the new prefix instead. When this is popped off, we continue working with the prefix now at the top. If at any time we come upon a character which cannot to added to the prefix at the top such that it remains a prefix of A, we clear the whole stack since none of the prefixes in the stack can be augmented to form A. Note that we do not actually need to store the prefixes, we can simply use integers to denote the length of the prefixes instead.

The following pseudocode follows this algorithm.

st = empty stack
count = 0

for i in range 0 to B.length-1
    if B[i] == A[0]
        push 1 onto st
    else if st is not empty and B[i] == A[st.top]
        st.top = st.top + 1
    else
        clear st

    if st is not empty and st.top == A.length
        count = count + 1
        pop st

Complexity of this approach is \mathcal{O}(|A|+|B|).

AUTHOR’S SOLUTION:

Author’s solution can be found here.

1 Like