Hàm Xâu

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho xâu có $n$ ký tự (đánh số từ $1$ ). Tính hai hàm xâu:

$z (i)$ : độ dài xâu con dài nhất bắt đầu tại vị trí $i$ đồng thời là tiền tố của xâu. Quy ước $z (1) = 0$ .
$π (i)$ : độ dài xâu con dài nhất kết thúc tại vị trí $i$ , đồng thời là tiền tố của xâu, và có độ dài tối đa $i - 1$ .

Một dòng duy nhất chứa xâu có độ dài $n$ .

Dòng đầu tiên in ra $n$ giá trị $z (1), z (2), \dots, z (n)$ .

Dòng thứ hai in ra $n$ giá trị $π (1), π (2), \dots, π (n)$ .

Input	Output	Giải thích
abaabca	0 0 1 2 0 0 1 0 0 1 1 2 0 1	Z-function và prefix function của xâu

Bình luận

Không có bình luận tại thời điểm này.