Kiểm tra mảng, chuỗi có tuần hoàn không

#1

vd: cho mảng 123123 >> là mảng tuần hoàn
12341234123 >> không tuần hoàn

em phân tích như này có đúng không mong các anh nhận xét:
1 mảng sẽ là tuần hoàn là mảng được tạo nên từ các mảng con ,mà các mảng con đó có cùng chiều dài , thứ tự phần tử, và các phần tử như nhau

mảng con ngắn nhất là mảng 1 phần tử
mảng con dài nhất là mảng ban đầu

vậy thì mình sẽ phải xét , từng mảng con với số lượng từ 1 đến n/2 , n/2 vì mảng con dài nhất nếu xuất hiện tuần hoàn là n/2 , nếu chỉ cần xuất hiện sự tuần hoàn trong lúc xét thì ta dừng lại và xác định mảng ban đầu là tuần hoàn

còn nếu không thì cứ xét cho đến n/2

vd: 123456123456123456
thì mình sẽ xét mảng con 1 ptu >> ko tuần hoàn
thì mình sẽ xét mảng con 2 ptu >> ko tuần hoàn
…
đến 6 ptu >> tuần hoàn >> mảng ban đầu tuần hoàn

#2

Bạn đăng đầy đủ đề bài kèm limit lên xem nào.

Bạn đánh giá thuật toán của bạn có độ phức tạp bao nhiêu?

#3

nếu chuỗi s’ là chuỗi con n’ kí tự của chuỗi s có n kí tự và s’ lặp đi lặp lại thì n phải chia hết cho n’. Vậy n’ là ước của n, vậy chỉ cần lặp n’ từ 1 tới căn(n) là đủ đâu cần tới n/2 :V

nếu n chia hết n’ thì kiểm tra s’ có tuần hoàn hay ko mất O(n) time, vậy tổng cộng mất O(\sqrt{n}) + O(n)\omega(n) với \omega(n) là hàm tính số ước nguyên tố của n. Theo https://math.stackexchange.com/questions/1217411/number-of-distinct-prime-divisors-of-an-integer-n-is-o-log-n-log-log-n thì hàm này là O\left(\frac{logn}{loglogn}\right) vậy tìm kiếm kiểu này chỉ tốn có O(\sqrt{n}) + O(n)\omega(n) = O\left(n\frac{logn}{loglogn}\right) thôi :V

edit: ủa đâu hình như phải xét tới n/2 thật :V :V :V ví dụ n=100 xét n’ tới 10 sao mà đủ :upside_down_face:

xét n’ tới n/2 thì tốn thành O(n) + O(n)d(n) với d(n) là hàm tính số ước của n :V Mà nếu phân tích n thành thừa số ng tố n = p_1^{e_1} * p_2^{e_2} * ... * p_k^{e_k} thì số ước của n là d(n) = (e_1 + 1) * (e_2 + 1) * ... * (e_k + 1) vậy có thể suy ra là d(n) = 2^{\omega(n)} :V :V Vậy cùng lắm là O(n^2), cận chặt hơn nữa là O\left(n2^{O\left(\frac{\log n}{\log\log n}\right)}\right)

ơ wiki người ta chứng minh đầy đủ hơn https://en.wikipedia.org/wiki/Divisor_function
ơ ghê vậy hình như đọc thấy d(n) = O(n \: \log\log n) vậy độ phức tạp bài này phải là O(n^2 \log\log n) chớ :V
ủa đọc tầm bậy số ước của n làm gì > n được :upside_down_face:

cái này mới đúng \limsup\limits_{n \to \infin}{\dfrac{\log d(n)}{\log n / \log\log n}} = \log 2. Vậy đpt vẫn là O\left(n2^{O\left(\frac{\log n}{\log\log n}\right)}\right)

edit: tìm được bài này trên leetcode: https://leetcode.com/problems/repeated-substring-pattern/description/ chỉ cho n = 10^4 mà submit thử thấy lẹ lắm vậy là lẹ hơn O(n^2) đúng rồi :V :V

1 Like
#4

ko có limit gì hết anh ơi, đề chỉ là kiểm tra xem mảng đầu vào có tuần hoàn hay không thôi, và nó cũng cho ví dụ thế thôi anh , nên em mới nghĩ cách đơn giản nhất là duyệt hết

#5

thanks anh, hay quá có bài tương tự luôn , hix mấy cái tính toán của anh em chịu @@ , em chỉ mới học lập trình thôi, thầy cho vài bài tập về tìm hướng giải quyết , rồi code , em mới tìm đc hướng thôi còn chưa biết code thế nào @@

bài trên leetcode anh cũng dùng duyệt trâu để làm à anh

#6

ờm nó dùng duyệt trâu, cho i chạy từ 1 tới n/2, nếu n chia hết cho i thì mới kiểm tra xem mảng con i phần tử có tuần hoàn hay ko

có ông này xài KMP O(n) nè https://takeitoutamber.medium.com/repeated-substring-pattern-leetcode-medium-problem-not-easy-kmp-and-robin-kare-ece91290d2c2

3 Likes
#7

Phân tích của bạn về mảng tuần hoàn là chính xác. Để kiểm tra xem một mảng có phải là mảng tuần hoàn hay không, bạn có thể thực hiện theo phương pháp sau:

  1. Xác định tỷ lệ của một “mảng con” trong mảng ban đầu. Mảng con là chuỗi các phần tử liên tiếp trong mảng.
  2. Bắt đầu từ mảng con có độ dài là 1 (một phần tử), tiếp theo là mảng con có độ dài là 2, và tiếp tục cho đến khi mảng con đạt đến n/2 phần tử, với n là độ dài của mảng ban đầu.
  3. Kiểm tra từng mảng con xem chúng có phải là mảng tuần hoàn hay không. Nếu có bất kỳ mảng con nào tuần hoàn, thì mảng ban đầu cũng là mảng tuần hoàn và quá trình kiểm tra có thể dừng lại.
  4. Nếu không có bất kỳ mảng con nào tuần hoàn, tiếp tục kiểm tra với mảng con dài hơn cho đến khi đạt đến n/2.

Ví dụ của bạn với mảng 123456123456123456 đã cho thấy quá trình kiểm tra từ mảng con 1 phần tử đến 6 phần tử và xác định được rằng mảng ban đầu là mảng tuần hoàn.

Phương pháp này là một cách hiệu quả để xác định xem một mảng có tuần hoàn hay không.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?