En uzun ortak alt dizi problemi olarak da karşılaşılan longest common subsequence problemini dynamic programming ile nasıl çözüleceğini içeren kodu bu sayfada bulabilirsiniz.
LCS Problemi ne diyenler için : http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
Dinamik Programlama ne diyenler için : /dinamik-programlama-dynamic-programming-nedir/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| *@author : tolpp | |
| */ | |
| public class LCS { | |
| public static void main(String[] args) { | |
| String x = "ZTR123AAAAB"; | |
| String y = "KLMN12BAB"; | |
| int M = x.length(); | |
| int N = y.length(); | |
| int[][] cozum = new int[M+1][N+1];// Altkümelerin harfler için ne kadar kere ortak olduğunu tuttuğum matrisim | |
| // LCS uzunluğunun ve tüm alt problemlerin dinamik programlamayla hesaplandığı kısım | |
| for (int i = M-1; i >= 0; i--) {//Dizi elemanlarını tersten gelerek kontrol ediyorum | |
| for (int j = N-1; j >= 0; j--) { | |
| if (x.charAt(i) == y.charAt(j)) | |
| cozum[i][j] = cozum[i+1][j+1] + 1;// eşleşme varsa bu harfin olduğu fazladan bir alt küme daha olduğunu belirtmek için matris üzerinde bu harflein bulunduğu konumdaki değeri 1 artırıyorum | |
| else | |
| cozum[i][j] = Math.max(cozum[i+1][j], cozum[i][j+1]);// Eşleşme yoksa, o ana kadarki en uzun altküme uzunluğunu en uzun altküme olarak alıyorum | |
| } | |
| } | |
| // cozum[][] matrisini kullanarak LCS nin bulunması | |
| int i = 0, j = 0; | |
| String out=""; | |
| while(i < M && j < N) { | |
| if (x.charAt(i) == y.charAt(j)) | |
| {// i ve j değerlerine göre x, y stringleri üzerinde dolaşarak eşleşme olup olmadığını kontrol ediyorum | |
| out += y.charAt(j); | |
| i++; | |
| j++; | |
| } | |
| else if (cozum[i+1][j] >= cozum[i][j+1]) i++;//her zaman en uzun alt kümeye gidebilmek için bu kontrolleri yapıyorum | |
| else j++; | |
| } | |
| System.out.println("LCS Length : "+out.length()); | |
| System.out.println("LCS : "+out); | |
| } | |
| } |
