SIMSTR - Đếm chuỗi tương tự
Xem dạng PDF
Gửi bài giải
Điểm:
3,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
- Với hai chuỗi a và b, ta định nghĩa sự giống nhau của các chuỗi là độ dài của tiền tố dài nhất chung cho cả hai chuỗi. Ví dụ với hai chuỗi "abc" và "abd" ta có độ giống nhau là 2, với hai chuỗi "aaa" và "aaab" ta có độ giống nhau là 3.
- Cho một xâu S, hãy tính độ giống nhau của các hậu tố của S
Input
- Dòng thứ nhất chứa một số nguyên n, là số bộ test (1 < n < 10)
- n dòng tiếp theo chứa các xâu S
Output
- Gồm n dòng, mỗi dòng in ra độ giống nhau của xâu
Sample
Input #1
2
ababaa
aa
Output #1
11
3
Hint
- Đối với trường hợp đầu tiên, các hậu tố của chuỗi là "ababaa", "babaa", "abaa", "baa", "aa" và "a". Điểm tương đồng của các chuỗi này với chuỗi "ababaa" lần lượt là 6,0,3,0,1, & 1. Như vậy, câu trả lời là 6 + 0 + 3 + 0 + 1 + 1 = 11
- Với trường hợp thứ hai, các hậu tố của chuỗi là: "11","1". Điểm tương đồng của các chuỗi này với 11 là: 1 + 2 = 3
Bình luận
Hint sai r admin ơi