Chương trình tìm số lượng chuỗi con khác nhau trong chuỗi cho trước trong Python

Cho chuỗi s, tìm số lượng chuỗi con duy nhất (distinct substrings).

Ví dụ: s = 'prrstvt', đầu ra = 26.

Các chuỗi con khác nhau: 'pr', 'rrs', 'st', 'rr', 'tv', 'rstv', 'stvt', 'prrstv', 'prrstvt', 'rrstvt', 's', 'prrst', 'stv', 'rrstv', 'rst', 'v', 'tvt', 'rstvt', 'r', 'rs', 'vt', 't', 'prr', 'p', 'rrst', 'prrs'.

Giải pháp

Sử dụng dynamic programming: với mỗi vị trí, mở rộng các chuỗi con kết thúc tại vị trí trước:

• visited := map mới
• Với mỗi index ind, value let trong s:
  • temp := tập hợp mới
  • Nếu ind-1 trong visited:
    • Với mỗi has_let trong visited[ind-1]: thêm has_let+let vào temp
  • Thêm let vào temp
  • visited[ind] := temp
• res := tập hợp mới
• Với mỗi sets trong visited: res.update(visited[sets])
• Trả về kích thước res

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(s):
    visited = dict()
    for ind, let in enumerate(s):
        temp = set()
        if ind-1 in visited:
            for has_let in visited[ind-1]:
                temp.add(has_let+let)
        temp.add(let)
        visited[ind] = temp
    res = set()
    for sets in visited:
        res.update(visited[sets])
    return len(res)

print(solve('prrstvt'))

Đầu vào

'prrstvt'

Đầu ra

26