უგრძესი საერთო ქვემიმდევრობის ამოცანა

უგრძესი საერთო ქვემიმდევრობის (უსქ) ამოცანა — ამოცანა, რომელიც ეძებს მიმდევრობებს შორის უგრძეს საერთო ქვემიმდევრობას (ძირითადად ორ მიმდევრობაზე განიხილავენ).

მაგალითად, განვიხილოთ ორი მიმდევრობა (ABCD) და (ACBAD). მათ 5 უსქ აქვთ, სიგრძით 2: (AB),(AC),(AD),(BD) და (CD); 2 უსქ, სიგრძით 3: (ABD) და (ACD); უფრო გრძელი კი არ გვაქვს. შესაბამისად, (ABC) და (ACD) არის უგრძესი საერთო ქვემიმდევრობა.

სირთულე

ეს ამოცანა არის NP-რთული ამოცანა. ის დინამიური პროგრამირების პრინციპით პოლინომიურ დროში იხსნება.

მოცემულია $N$ სიგრძეების მიმდევრობები $n_1,...,n_N$, სრული ძებნა შეამოწმებს თითოეულ მათგანის $2^{n_1}$ ქვესიმრავლეს, რათა დაადგინოს, არიან თუ არა ისინი აგრეთვე დანარჩენი მიმდევრობების ქვემიმდევრობები; მოცემული ამოცანის დროის სირთულე იქნება

$O\left(2^{n_1}\sum _{i>1}{n}_i\right).$

n და m სიგრძის ორი მიმდევრობისთვის დროის სირთულე დინამიური პროგრამირებით იქნება O(n × m). ნებისმიერი რაოდენობის ქვემიმდევრობისთვის დინამიური პროგრამირების ამოხსნის დროის სირთულე იქნება

$O\left(N\prod _{i=1}^N{n}_i\right).$

ამოხსნა ორი მიმდევრობისთვის

LCS ფუნქცია

განვსაზღვროთ ორი მიმდევრობა შემდეგნაირად: $X=(x_1{x}_2\cdots x_m)$ და $Y=(y_1{y}_2\cdots y_n)$ . $X$-ის პრეფიქსები არიან $X_{1,2,\dots ,m}$ ; $Y$-ის კი $Y_{1,2,\dots ,n}$ .$𝐿𝐶𝑆(X_i,Y_j)$ -ით აღვნიშნოთ უგრძესი საერთო ქვემიმდევრობა პრეფიქსებისთვის $X_i$ და $Y_j$ .

$𝐿𝐶𝑆(X_i,Y_j)=\{\begin{array}{cc}\mathrm{\varnothing }& \text{თუ }i=0\text{ ან }j=0\\ 𝐿𝐶𝑆(X_{i-1},Y_{j-1})+1& \text{თუ }i,j>0\text{ და }{x}_i=y_j\\ \max \{𝐿𝐶𝑆(X_i,Y_{j-1}),𝐿𝐶𝑆(X_{i-1},Y_j)\}& \text{თუ }i,j>0\text{ და }{x}_i\ne y_j.\end{array}$

რათა ვიპოვოთ LCS $X_i$ და $Y_j$-თვის, შევადაროთ $x_i$ და $y_j$. თუ ისინი ტოლია, მაშინ ქვემიმდევრობა $𝐿𝐶𝑆(X_{i-1},Y_{j-1})$ -ზე ერთით მეტი იქნება . თუ ისინი ტოლი არ არიან, მაშინ $𝐿𝐶𝑆(X_i,Y_{j-1})$, და $𝐿𝐶𝑆(X_{i-1},Y_j)$ შორის უგრძესის ტოლი გახდება.

იმპლემენტაცია C++-ზე

int dp[1000][1000];
int getLCS(vector<int>a,vector<int>b){
    int n=a.size();
    int m=b.size();
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=1+dp[i-1][j-1];
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }return dp[n][m];
}

რესურსები ინტერნეტში

• Dictionary of Algorithms and Data Structures: longest common subsequence
• A collection of implementations of the longest common subsequence in many programming languages
• Implementation of Longest Common Subsequence Algorithm in C Programming Language