rust_algorithms/dp/sequences.rs
1//! Ketma-ketliklar ustidagi DP: LCS, LIS, Levenshtein, Kadane.
2
3/// **LCS** — eng uzun umumiy ketma-ketlik uzunligi (Longest Common Subsequence).
4///
5/// "Ketma-ketlik" (subsequence) — belgilarni **tartibini buzmasdan**, lekin
6/// oralaridan tashlab olish mumkin. `"olma"` va `"alma"` uchun LCS = `"lma"`.
7///
8/// **Holat:** `dp[i][j]` = `a[..i]` va `b[..j]` ning LCS uzunligi.
9/// **O'tish:**
10/// ```text
11/// a[i-1] == b[j-1] → dp[i][j] = dp[i-1][j-1] + 1
12/// aks holda → dp[i][j] = max(dp[i-1][j], dp[i][j-1])
13/// ```
14///
15/// - **Time:** O(n·m), **Space:** O(m) — faqat oldingi qatorni saqlaymiz.
16///
17/// **Qayerda ishlatiladi:** `git diff`, DNA ketma-ketliklarini solishtirish,
18/// fayl solishtiruvchi dasturlar.
19///
20/// # Misol
21/// ```
22/// use rust_algorithms::dp::lcs_len;
23///
24/// assert_eq!(lcs_len("olma", "alma"), 3);
25/// assert_eq!(lcs_len("ABCBDAB", "BDCABA"), 4);
26/// assert_eq!(lcs_len("abc", "xyz"), 0);
27/// ```
28pub fn lcs_len(a: &str, b: &str) -> usize {
29 let a: Vec<char> = a.chars().collect();
30 let b: Vec<char> = b.chars().collect();
31 let mut oldingi = vec![0usize; b.len() + 1];
32 let mut hozirgi = vec![0usize; b.len() + 1];
33
34 for i in 1..=a.len() {
35 for j in 1..=b.len() {
36 hozirgi[j] = if a[i - 1] == b[j - 1] {
37 oldingi[j - 1] + 1
38 } else {
39 oldingi[j].max(hozirgi[j - 1])
40 };
41 }
42 std::mem::swap(&mut oldingi, &mut hozirgi);
43 }
44 oldingi[b.len()]
45}
46
47/// LCS ning **o'zini** (satr sifatida) qaytaradi.
48///
49/// To'liq 2D jadval kerak (O(n·m) xotira), chunki orqaga yurib tiklaymiz.
50///
51/// # Misol
52/// ```
53/// use rust_algorithms::dp::lcs;
54///
55/// assert_eq!(lcs("olma", "alma"), "lma");
56/// assert_eq!(lcs("AGGTAB", "GXTXAYB"), "GTAB");
57/// assert_eq!(lcs("", "abc"), "");
58/// ```
59pub fn lcs(a: &str, b: &str) -> String {
60 let ac: Vec<char> = a.chars().collect();
61 let bc: Vec<char> = b.chars().collect();
62 let (n, m) = (ac.len(), bc.len());
63 let mut dp = vec![vec![0usize; m + 1]; n + 1];
64
65 for i in 1..=n {
66 for j in 1..=m {
67 dp[i][j] = if ac[i - 1] == bc[j - 1] {
68 dp[i - 1][j - 1] + 1
69 } else {
70 dp[i - 1][j].max(dp[i][j - 1])
71 };
72 }
73 }
74
75 // Orqaga yurib javobni yig'amiz
76 let mut natija = Vec::with_capacity(dp[n][m]);
77 let (mut i, mut j) = (n, m);
78 while i > 0 && j > 0 {
79 if ac[i - 1] == bc[j - 1] {
80 natija.push(ac[i - 1]);
81 i -= 1;
82 j -= 1;
83 } else if dp[i - 1][j] >= dp[i][j - 1] {
84 i -= 1;
85 } else {
86 j -= 1;
87 }
88 }
89 natija.reverse();
90 natija.into_iter().collect()
91}
92
93/// **LIS** — eng uzun qat'iy o'suvchi ketma-ketlik uzunligi, **O(n log n)** da.
94///
95/// **G'oya (sabr o'yini / patience sorting):** `tails[k]` — uzunligi `k+1` bo'lgan
96/// o'suvchi ketma-ketliklar orasida **eng kichik** oxirgi element.
97/// Har bir yangi son uchun `tails` da binary search qilib, uni almashtiramiz
98/// yoki oxiriga qo'shamiz.
99///
100/// ```text
101/// [10, 9, 2, 5, 3, 7, 101, 18]
102/// tails: [10] → [9] → [2] → [2,5] → [2,3] → [2,3,7] → [2,3,7,101] → [2,3,7,18]
103/// javob: 4
104/// ```
105///
106/// > `tails` massivi LIS ning o'zi **emas** — faqat uzunligi to'g'ri.
107/// > Haqiqiy ketma-ketlik uchun [`lis`] dan foydalaning.
108///
109/// - **Time:** O(n log n), **Space:** O(n).
110///
111/// # Misol
112/// ```
113/// use rust_algorithms::dp::lis_len;
114///
115/// assert_eq!(lis_len(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
116/// assert_eq!(lis_len(&[7, 7, 7]), 1);
117/// assert_eq!(lis_len(&[]), 0);
118/// ```
119pub fn lis_len(nums: &[i64]) -> usize {
120 let mut tails: Vec<i64> = Vec::new();
121 for &x in nums {
122 match tails.binary_search(&x) {
123 Ok(_) => {} // takror — qat'iy o'sish buziladi
124 Err(pos) if pos == tails.len() => tails.push(x), // yangi eng uzun
125 Err(pos) => tails[pos] = x, // ketma-ketlikni "arzonlashtiramiz"
126 }
127 }
128 tails.len()
129}
130
131/// LIS ning **o'zini** qaytaradi (O(n log n), ota indekslarini saqlab).
132///
133/// # Misol
134/// ```
135/// use rust_algorithms::dp::lis;
136///
137/// assert_eq!(lis(&[10, 9, 2, 5, 3, 7, 101, 18]), vec![2, 3, 7, 18]);
138/// assert_eq!(lis(&[3, 2, 1]), vec![1]);
139/// ```
140pub fn lis(nums: &[i64]) -> Vec<i64> {
141 if nums.is_empty() {
142 return Vec::new();
143 }
144 let mut tails_idx: Vec<usize> = Vec::new(); // tails[k] ga mos asl indeks
145 let mut ota: Vec<Option<usize>> = vec![None; nums.len()];
146
147 for i in 0..nums.len() {
148 // nums[i] uchun tails ichidan o'rin topamiz (lower_bound)
149 let pos = tails_idx.partition_point(|&j| nums[j] < nums[i]);
150 if pos > 0 {
151 ota[i] = Some(tails_idx[pos - 1]);
152 }
153 if pos == tails_idx.len() {
154 tails_idx.push(i);
155 } else {
156 tails_idx[pos] = i;
157 }
158 }
159
160 let mut natija = Vec::new();
161 let mut kursor = tails_idx.last().copied();
162 while let Some(i) = kursor {
163 natija.push(nums[i]);
164 kursor = ota[i];
165 }
166 natija.reverse();
167 natija
168}
169
170/// **Levenshtein masofasi** — bir satrni ikkinchisiga aylantirish uchun kerak
171/// bo'lgan minimal amallar soni (qo'shish, o'chirish, almashtirish).
172///
173/// **Holat:** `dp[i][j]` = `a[..i]` ni `b[..j]` ga aylantirish narxi.
174/// **O'tish:** belgilar teng bo'lsa — bepul; aks holda uchta variantning eng arzoni:
175///
176/// ```text
177/// dp[i][j] = 1 + min( dp[i-1][j] ← o'chirish
178/// dp[i][j-1] ← qo'shish
179/// dp[i-1][j-1] ← almashtirish )
180/// ```
181///
182/// - **Time:** O(n·m), **Space:** O(m).
183///
184/// **Qayerda ishlatiladi:** imlo tuzatgich ("shunday demoqchimidingiz?"),
185/// DNA tahlili, fuzzy qidiruv.
186///
187/// # Misol
188/// ```
189/// use rust_algorithms::dp::edit_distance;
190///
191/// assert_eq!(edit_distance("kitten", "sitting"), 3);
192/// assert_eq!(edit_distance("salom", "salom"), 0);
193/// assert_eq!(edit_distance("", "abc"), 3);
194/// assert_eq!(edit_distance("olma", "alma"), 1);
195/// ```
196pub fn edit_distance(a: &str, b: &str) -> usize {
197 let ac: Vec<char> = a.chars().collect();
198 let bc: Vec<char> = b.chars().collect();
199 let m = bc.len();
200
201 let mut oldingi: Vec<usize> = (0..=m).collect(); // bo'sh satrdan b[..j] ga: j ta qo'shish
202 let mut hozirgi = vec![0usize; m + 1];
203
204 for i in 1..=ac.len() {
205 hozirgi[0] = i; // a[..i] dan bo'sh satrga: i ta o'chirish
206 for j in 1..=m {
207 hozirgi[j] = if ac[i - 1] == bc[j - 1] {
208 oldingi[j - 1]
209 } else {
210 1 + oldingi[j].min(hozirgi[j - 1]).min(oldingi[j - 1])
211 };
212 }
213 std::mem::swap(&mut oldingi, &mut hozirgi);
214 }
215 oldingi[m]
216}
217
218/// **Kadane algoritmi** — eng katta yig'indili qism-massiv (maximum subarray).
219///
220/// **G'oya:** har bir pozitsiyada bitta savol beramiz — "oldingi yig'indini davom
221/// ettirish foydalimi yoki shu yerdan yangi boshlash yaxshiroqmi?"
222/// Agar oldingi yig'indi manfiy bo'lsa, uni sudrab yurishdan foyda yo'q.
223///
224/// - **Time:** O(n), **Space:** O(1) — DP ning eng nafis namunasi.
225///
226/// Qaytadi: `(yig'indi, boshlanish_indeksi, tugash_indeksi_inklyuziv)`.
227/// Bo'sh massivda `None`.
228///
229/// # Misol
230/// ```
231/// use rust_algorithms::dp::max_subarray;
232///
233/// let v = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
234/// assert_eq!(max_subarray(&v), Some((6, 3, 6))); // [4, -1, 2, 1]
235///
236/// // hammasi manfiy bo'lsa — eng katta (eng kam manfiy) element
237/// assert_eq!(max_subarray(&[-5, -2, -9]), Some((-2, 1, 1)));
238/// assert_eq!(max_subarray(&[]), None);
239/// ```
240pub fn max_subarray(nums: &[i64]) -> Option<(i64, usize, usize)> {
241 if nums.is_empty() {
242 return None;
243 }
244 let mut eng_yaxshi = nums[0];
245 let (mut bosh, mut oxir) = (0usize, 0usize);
246
247 let mut hozirgi = nums[0];
248 let mut hozirgi_bosh = 0usize;
249
250 for i in 1..nums.len() {
251 if hozirgi < 0 {
252 hozirgi = nums[i]; // yangidan boshlaymiz
253 hozirgi_bosh = i;
254 } else {
255 hozirgi += nums[i];
256 }
257 if hozirgi > eng_yaxshi {
258 eng_yaxshi = hozirgi;
259 bosh = hozirgi_bosh;
260 oxir = i;
261 }
262 }
263 Some((eng_yaxshi, bosh, oxir))
264}
265
266#[cfg(test)]
267mod tests {
268 use super::*;
269 use crate::util::Rng;
270
271 #[test]
272 fn lcs_uzunlik_va_ozi_mos() {
273 let juftliklar = [
274 ("olma", "alma"),
275 ("AGGTAB", "GXTXAYB"),
276 ("", ""),
277 ("abc", ""),
278 ("abcdef", "abcdef"),
279 ("dynamic", "programming"),
280 ];
281 for (a, b) in juftliklar {
282 assert_eq!(lcs(a, b).chars().count(), lcs_len(a, b), "{a} / {b}");
283 }
284 }
285
286 #[test]
287 fn lcs_haqiqiy_ketma_ketlik() {
288 let (a, b) = ("ABCBDAB", "BDCABA");
289 let natija = lcs(a, b);
290 // natija ikkala satrning ham qism ketma-ketligi bo'lishi kerak
291 for s in [a, b] {
292 let mut it = s.chars();
293 assert!(natija.chars().all(|c| it.any(|x| x == c)), "{natija} ⊄ {s}");
294 }
295 }
296
297 #[test]
298 fn lis_uzunlik_va_ozi_mos() {
299 let mut rng = Rng::new(808);
300 for _ in 0..50 {
301 let v = rng.vec(60, -50, 50);
302 let ketma_ketlik = lis(&v);
303 assert_eq!(ketma_ketlik.len(), lis_len(&v));
304 assert!(ketma_ketlik.windows(2).all(|w| w[0] < w[1]));
305 }
306 }
307
308 #[test]
309 fn lis_chegaraviy() {
310 assert_eq!(lis_len(&[1]), 1);
311 assert_eq!(lis_len(&[5, 4, 3, 2, 1]), 1);
312 assert_eq!(lis_len(&[1, 2, 3, 4, 5]), 5);
313 assert!(lis(&[]).is_empty());
314 }
315
316 #[test]
317 fn levenshtein_xossalari() {
318 assert_eq!(edit_distance("", ""), 0);
319 // simmetriklik
320 assert_eq!(
321 edit_distance("kitten", "sitting"),
322 edit_distance("sitting", "kitten")
323 );
324 // uchburchak tengsizligi
325 let (a, b, c) = ("olma", "alma", "salom");
326 assert!(edit_distance(a, c) <= edit_distance(a, b) + edit_distance(b, c));
327 }
328
329 #[test]
330 fn kadane_bruteforce_bilan_mos() {
331 let mut rng = Rng::new(909);
332 for _ in 0..50 {
333 let v = rng.vec(40, -20, 20);
334 let (yigindi, bosh, oxir) = max_subarray(&v).unwrap();
335
336 // sodda O(n²) tekshiruv
337 let mut kutilgan = i64::MIN;
338 for i in 0..v.len() {
339 let mut s = 0;
340 for x in &v[i..] {
341 s += x;
342 kutilgan = kutilgan.max(s);
343 }
344 }
345 assert_eq!(yigindi, kutilgan);
346 assert_eq!(v[bosh..=oxir].iter().sum::<i64>(), yigindi);
347 }
348 }
349}