Cho chuỗi s, tìm chuỗi ngắn nhất t, sao cho, t^m = s.Cho chuỗi s, tìm chuỗi ngắn nhất t, sao cho, t^m = s
Ví dụ:
s="aabbb" => t="aabbb"
s="abab" => t = "ab"
Nhanh như thế nào nó có thể được thực hiện?
Tất nhiên ngây thơ, đối với mỗi m chia | s |, tôi có thể thử nếu chuỗi con (s, 0, | s |/m)^m = s.
Người ta có thể tìm ra giải pháp trong thời gian O (d (| s |) n), trong đó d (x) là số ước của s. Nó có thể được thực hiện hiệu quả hơn?
Đây là vấn đề tính toán thời gian của chuỗi. Knuth, Morris and Pratt's sequential string matching algorithm là một nơi tốt để bắt đầu. Đây là một bài viết có tựa đề "Ghép mẫu nhanh trong chuỗi" từ năm 1977.
Nếu bạn muốn làm quen với nó, hãy xem bài báo "Tìm tất cả các giai đoạn và Palindromes ban đầu của chuỗi trong song song" của Breslauer và Galil năm 1991. Từ tóm tắt của họ:
Thời gian tối ưu O (log log n) Thuật toán CRCW-PRAM tính toán tất cả khoảng thời gian của một chuỗi được trình bày. Các thuật toán song song trước đây tính toán khoảng thời gian chỉ khi nó ngắn hơn một nửa chiều dài của chuỗi . Thuật toán này có thể được sử dụng để tìm tất cả các palindromes ban đầu của một chuỗi trong cùng một thời gian và giới hạn bộ xử lý. Cả hai thuật toán là nhanh nhất có thể trên bảng chữ cái chung. Chúng tôi nhận được một ràng buộc thấp hơn để tìm palindromes bởi một sửa đổi của một thấp hơn trước đây được biết đến ràng buộc cho việc tìm kiếm thời gian của một chuỗi [3]. Khi các bộ xử lý p là , các giới hạn có thể trở thành \ Theta (d n p e + nhật ký log d1 + p = ne 2p).
một sửa đổi để Boyer-Moore có thể có thể xử lý này trong thời gian O (n) trong đó n là chiều dài của s
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
Có bạn có thể làm điều đó trong thời gian O(|s|).
Bạn có thể tìm kiếm chuỗi "mục tiêu" có độ dài n trong chuỗi "nguồn" có độ dài m trong thời gian O(n+m). Xây dựng một giải pháp dựa trên đó.
Cho cả nguồn và mục tiêu là s. Một ràng buộc bổ sung là 1 và bất kỳ vị trí nào trong nguồn không phân chia |s| không phải là vị trí bắt đầu hợp lệ cho trận đấu. Tất nhiên, tìm kiếm sẽ luôn thất bại. Nhưng nếu có một phần phù hợp và bạn đã đạt đến cuối chuỗi sourse, sau đó bạn có một giải pháp cho vấn đề ban đầu.
Tôi thực sự thích điều này gọi là z-thuật toán: http://www.utdallas.edu/~besp/demo/John2010/z-algorithm.htm
Đối với mỗi vị trí của nó tính toán chuỗi con dài nhất bắt đầu từ đó, đó cũng là một tiền tố của toàn bộ chuỗi. (trong thời gian tuyến tính tất nhiên).
a a b c a a b x a a a z
1 0 0 3 1 0 0 2 2 1 0
Với "bảng z" này, thật dễ dàng để tìm tất cả các chuỗi có thể được tính theo toàn bộ điều. Chỉ cần kiểm tra tất cả các vị trí nếu pos+z[pos] = n.
Trong trường hợp của chúng tôi:
a b a b
0 2 0
Đây pos = 2 mang đến cho bạn 2+z[2] = 4 = n vì thế chuỗi ngắn nhất bạn có thể sử dụng là một trong những chiều dài 2.
Điều này thậm chí sẽ cho phép bạn tìm thấy trường hợp chỉ một tiền tố của các kết quả chuỗi được tính theo số mũ, như:
a b c a
0 0 1
Ở đây (abc)^2 có thể được cắt xuống gốc của bạn chuỗi. Nhưng tất nhiên, nếu bạn không muốn các trận đấu như thế này, chỉ cần đi qua các ước số.