LPS implementation. Longest proper prefix which is also suffix. Used in KMP string search algorithm

lps.py

class Solution(object):

    def lps(self, s):
        """
        Returns an array of the same length as s.
        The value at index i contains the count of
        the longest prefix of s (i.e. string starting
        at index 0) which matches the suffix ending
        at i.

        Prefixes must be proper (i.e. prefix
        and suffix cannot be equal)

        Runtime is O(n). Backtracking is O(n), since
        in order to backtrack k times, there must have
        been k number of continuous matches. Since there
        are O(n) continuous matches, there can only be O(n)
        backtracks.
        """
        lps = []
        n = len(s)
        if n == 0:
            return lps

        num_matched = 0
        lps.append(num_matched)

        i = 1
        while i < n:
            # If there is a match, extend the current streak
            if s[num_matched] == s[i]:
                num_matched += 1
                lps.append(num_matched)
                i += 1
            else:
                # If there is no streak and no match,
                # the lps is 0 for the index
                if num_matched == 0:
                    lps.append(0)
                    i += 1
                else:
                    # There is no match, but there is an existing streak.
                    # Backtrack to previous streaks that we may be able
                    # to extend
                    num_matched = lps[num_matched - 1]
        return lps