ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของเฮิร์ชเบิร์ก"

เราจะนิยาม[[โปรแกรมย่อยไปข้างหน้า]](Forward subprogram) ซึ่งคำนวณค่าของ Edit(Prefix[''x'',''i''],Prefix[''y'',''j'']) สำหรับทุกๆ ''i'' และ ''j'' คล้าย[[ขั้นตอนวิธีของนีดเดิ้ลแมน – วันช์]] และคืนค่า array{Edit(''x'',Prefix[''y'',''j''])}_{0 ≤ ''j'' ≤ ''m''} อีกส่วนหนึ่งที่เราจะนิยามคือ[[โปรแกรมย่อยถอยหลัง]](Backward subprogram) ซึ่งคล้ายกับโปรแกรมย่อยไปข้างหน้าแต่จะทำ[[โปรแกรมแบบพลวัติ]] (dynamic program) จะสลับทิศทางกัน โดยจะเริ่มจากซ้ายไปขวาและล่างขึ้นบนแทน ซึ่งโปรแกรมนี้จะคืนค่า array {Edit(''x'',Suffix[''y'',''j''])}_{0 ≤ ''j'' ≤ ''m''} โดย Suffix[''y'',''j''] คือ คำเสริมท้าย(suffix) ของสายอักขระ ''y'' ของความยาว ''j''

1. n = length(x); m = length(y)

2. Edit[Prefix[0,0]] = 0;

3. For all i from 1 to n:

4. For all j from 1 to m:

5. RETURN Edit[x] %% an array of length m+1

1. n = length(x); m = length(y)

2. For all i from 1 to n:

3. For all j from 1 to m:

4. RETURN Edit[x] %% an array of length m+1

1. n = length(x); m = length(y)

2. If n <= 1 or m <= 1:

* [[:en:Needleman-Wunsch algorithm]]

* [[:en:Smith Waterman algorithm]]

* [[:en:Levenshtein distance]]

* [[:en:Longest_common_subsequence_problemLongest common subsequence problem|Longest Common Subsequence]]