tìm xâu con

[bld]

xâu X là xâu đã được mã hóa theo cách tăng ord của mỗi kí tự trong xâu ban đầu chưa được mã hóa lên t đơn vị , t nằm trong khoảng -225..225.
tìm xem trong xâu ban đầu X' chưa được mã hóa thì xâu Y có thể xuất hiện nhiều nhất bao nhiêu lần .

inp:xâu X và Y
out:số lần xuất hiện

mọi người có thể cảm thấy khó hiểu ở đoạn không biết t thì làm sao giải mã rồi đếm được, giải thích như sau : có thể có nhiều t để xuất hiện xâu Y trong xâu X(nhiều trường hợp , với mỗi trường hợp thì số lần xuất hiện xâu Y trong xâu X là khác nhau) , ta cần đếm số lần xuất hiện nhiều nhất

[quangtq]

Hiểu rồi. Suy nghĩ đã
====================

[bld]

ko ai giải àh , bài này hay mà ^^, thấy hay mà ko giải thì uổng quá, nên mình đào mồ nó lên :p

[zeldery]

Bài này bạn sử dụng một vòng lặp t cho chạy từ 0 đến 255 (thực chất mấy số âm cũng ra những trường hợp này thôi), mã hoá xâu Y thành xâu Y', sau đó đếm số lần xuất hiện sâu Y' trong X' => số lần xuất hiện của Y trong X (mã hoá Y sẽ tiết kiệm hơn giải mã X). Tìm max của các lần xuất hiện đó thôi ^^

[quangtq]

Ặc. Nếu độ dài xâu mà lớn thì vét thế đến bao giờ.
Cực lâu

[linhhahaduc]

Có thể dùng thêm thuật toán KMP . Giảm độ phức tạp thành 256*(M+N) (M và N là độ dài xâu X và Y) :D

[bld]

thuật toán KMPlà thuật toán gì vậy a ?
bài này e giải theo kiểu tính độ chênh lệch của ord các kí tự trong xâu

[lqhuy93]

Thuật toán tìm kiếm chuỗi Knuth-Morris-Pratt (KMP) hiệu quả !
Bài này xét tất cả chuỗi độ dài Y(M) trong X(N) sau đó tính ORD, xem giá trị ORD nào xuất hiện nhièu lần nhất thì chọn cái đó. Độ phức tạp O ( (M-N+1)*N )

[bld]

e vẫn chưa hiểu lắm ,
cách làm của e:
nhận xét thấy rằng khi cộng ord vào các kí tự thì độ chênh lệch ord giữa 2 kí tự bạn đầu vẫn ko đổi
vd: AB cộng 2 vào ord -> CD , độ chênh lệch ord giữa C & D = giữa A & B

làm thử : với X=ABCDEFGH
Y= LMN
ta có mảng A với độ lớn length(X)-1 (A[i] là chênh lệch ord giữa X[i] và X[i+1]
A= 1,1,1,1,1,1,1
mảng B tương tự với xâu Y
B=1,1
như vậy chỉ cần tìm mảng B trong mảng A . + 1 chút xử lý là dc.
bài này chỉ cần O(length(X)) là dc (dùng lùa bò vào chuồng)
-> có thể tìm dc t luôn

[quangtq]

Hay nhỉ. Thế mà mình không nghĩ ra. Thật là gà

[technolt]

@linhhahaduc: Chém ghê vậy đệ :D
@bld: KMP là thuật toán so khớp chuỗi, tìm sự xuất hiện của pattern trong string. Google ra một đống!