https://oj.luyencode.net/problem/DPSUBSTR3

[utterances-bot]

Xâu con giống nhau - Luyện Code Online

https://oj.luyencode.net/problem/DPSUBSTR3

[trantrunghieu123]

Đây là gợi ý theo cách giải của mình cho những người đã cố gắng nhưng không thành công

Gợi ý

Ta nhận thấy bài này có thể hiểu là đếm số xâu con chung (khác rỗng) có thể tạo thành từ xâu 1 và xâu 2. Bài này có chút giống xâu con chung dài nhất ở phần xâu con chung nhưng mình nghĩ sẽ khác 1 chút ở công thức và cách dùng bảng qhđ.

cách gọi dp[i,j]

Gọi dp[i,j] là số lượng xâu chung có thể có của i kí tự đầu thuộc xâu 1 và j kí tự đầu thuộc xâu 2. Vd: xâu 1: abbb , xâu 2:aaaaa dp[1,2] sẽ là số lượng xâu con chung của "a" và "aa" : 2 đó là (a,a và a,a)

Còn đây sẽ là vd cho công thức tính dp[i,j]

ví dụ

Điều kiện trước tiên là s[i]=s[j] , ai không hiểu thì xem lại bài xâu con chung dài nhất Vd: xâu 1: aba , xâu 2:ba Thì dp[2,1] sẽ là 1 (b,b) Ở dp[3,2] thì xâu 1[3] là a, còn xâu 2[2] là a , 2 kí tự giống nhau , ta tính tay thì nó sẽ là 3 : a,b,ba Trùng hợp thay dp[2,1] là 1(b) Nếu ta thêm a vào b sẽ ra ba . Đồng thời a cũng là xâu.

Đó là gợi ý của mình , các bạn xem thử có mở thêm nút thắt nào không.

[anle12345]

Bài này ai code theo ý tưởng của anh trantrunghieu123 thì cẩn thận phần chia dư nhé. Tại chia dư ở đây có phép trừ , chia dư sai kết quả ra số âm :)) Code này thì không phải mình code , mình xem ý tưởng của anh trên kia thôi . Mình chia sẻ code này , các bạn tham khảo nếu dùng pascal tại code này làm bằng pascal. Đây là lời giải của mình đã AC. Nếu bạn đã cố gắng mà chưa làm được thì có thể tham khảo lời giải của mình.

Xem code AC

uses crt; const r=1000000007; var i,n,m,j:int64; s1,s2:ansistring; f:array[0..5000,0..5000] of int64; function tru(a,b:int64):int64; begin ---a:=a-b; ---while a<0 do a:=a+r; ---a:=a mod r; exit(a); end; begin clrscr; readln(s1); readln(s2); n:=length(s1); m:=length(s2); for i:=1 to n do ----------for j:=1 to m do --------------begin ----------------f[i,j]:=tru(f[i-1,j]+f[i,j-1],f[i-1,j-1]) mod r; ----------------if s1[i]=s2[j] then f[i,j]:=(f[i,j]+f[i-1,j-1]+1) mod r; --------------end; clrscr; writeln(f[n,m]); // code dựa nhiều phần vào gợi ý của trantrunghieu123 readln; end.