def compute_lps_array(pattern):
    """Return the `lps` array for given the string `pattern`.
    This means that `lps[i]` is the longest proper prefix of `pattern[0:i]`
    which is also a suffix of `pattern[0:i]`.

    The efficiency of this algorithm is O(M), where M is the length
    of pattern.

    Example:
        pattern:  | a | b | a | b | a | b | c | a |
        index:    | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
        value:    | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
    """
    m = len(pattern)
    lps = [0] * m
    j = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[j]:
            j += 1
            lps[i] = j
            i += 1
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                lps[i] = 0
                i += 1
    return lps