Prefixes and Suffixes (Codeforces 432D)
Tags: DP, string suffix structures

You have a string s = s1s2...s|s|, where |s| is the length of string s, and si its i-th character. Let's introduce several definitions:  A substring s[i..j] (1 ≤ i ≤ j ≤ |s|) of string s is string sisi + 1...sj.  The prefix of string s of length l (1 ≤ l ≤ |s|) is string s[1..l].  The suffix of string s of length l (1 ≤ l ≤ |s|) is string s[|s| - l + 1..|s|]. Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.

Input: The single line contains a sequence of characters s1s2...s|s| (1 ≤ |s| ≤ 105) — string s. The string only consists of uppercase English letters.

Output: In the first line, print integer k (0 ≤ k ≤ |s|) — the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers li ci. Numbers li ci mean that the prefix of the length li matches the suffix of length li and occurs in string s as a substring ci times. Print pairs li ci in the order of increasing li.


Sample Inputs:
ABACABA

AAA

Sample Outputs:
3
1 4
3 2
7 1

3
1 3
2 2
3 1

Solution (Python):
from collections import Counter

def lps(S: str) -> list:
    n = len(S)
    LPS = [0] * n
    for i in range(1, n):
        j = LPS[i - 1]
        while j > 0 and S[j] != S[i]:
            j = LPS[j - 1]
        if S[i] == S[j]:
            j += 1
        LPS[i] = j
    return LPS

def is_pallindrome(S) -> bool:
    (start, end) = (0, len(S) - 1)
    while start < end:
        if S[start] != S[end]:
            break
        start += 1
        end -= 1
    return True

def main(S):
    n = len(S)
    LPS = lps(S)
    count = [0] * (n + 1)
    for i in range(n):
        count[LPS[i]] += 1
    for i in range(n - 1, 0, -1):
        count[LPS[i - 1]] += count[i]
    for i in range(n + 1):
        count[i] += 1
    ans = []
    pref = LPS[n - 1]
    while pref > 0:
        ans.append((pref, count[pref]))
        pref = LPS[pref - 1]
    ans.append((n, 1))
    ans.sort()
    return f'{len(ans)}\n' + '\n'.join((f'{l} {c}' for (l, c) in ans))
if __name__ == '__main__':
    t = 1
    ans = []
    for i in range(t):
        s = input()
        ans.append(main(s))
    for i in ans:
        print(i)

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    s = readStr()
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    ans = [1] * n
    for i in range(n - 1, -1, -1):
        j = pi[i]
        if j:
            ans[j - 1] += ans[i]
    tar = [n]
    j = n - 1
    while pi[j]:
        tar.append(pi[j])
        j = pi[j] - 1
    tar = tar[::-1]
    print(len(tar))
    for idx in tar:
        print(idx, ans[idx - 1])
    return
solve()

Solution (Python):
def getSolution(s):
    lenS = len(s)
    p = [0]
    solution = ''
    for i in range(1, lenS):
        j = p[i - 1]
        while j > 0 and s[j] != s[i]:
            j = p[j - 1]
        if s[j] == s[i]:
            j += 1
        p.append(j)
    result = []
    temp = lenS
    while temp != 0:
        result += [temp]
        temp = p[temp - 1]
    count = [0] * (lenS + 1)
    for i in range(lenS):
        count[p[i]] += 1
    for i in range(lenS - 1, 1, -1):
        count[p[i - 1]] += count[i]
    for i in result[::-1]:
        solution += str(i) + ' ' + str(count[i] + 1) + '\n'
    print(len(result))
    print(solution)
s = input()
getSolution(s)