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

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

მაგალითად, განვიხილოთ ორი მიმდევრობა (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}$ .${\mathit {LCS}}(X_{i},Y_{j})$ -ით აღვნიშნოთ უგრძესი საერთო ქვემიმდევრობა პრეფიქსებისთვის $X_{i}$ და $Y_{j}$ .

${\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\emptyset &{\mbox{თუ }}i=0{\mbox{ ან }}j=0\\{\mathit {LCS}}(X_{i-1},Y_{j-1})+1&{\mbox{თუ }}i,j>0{\mbox{ და }}x_{i}=y_{j}\\\operatorname {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS}}(X_{i-1},Y_{j})\}&{\mbox{თუ }}i,j>0{\mbox{ და }}x_{i}\neq y_{j}.\end{cases}}$

რათა ვიპოვოთ LCS $X_{i}$ და $Y_{j}$-თვის, შევადაროთ $x_{i}$ და $y_{j}$. თუ ისინი ტოლია, მაშინ ქვემიმდევრობა ${\mathit {LCS}}(X_{i-1},Y_{j-1})$ -ზე ერთით მეტი იქნება . თუ ისინი ტოლი არ არიან, მაშინ ${\mathit {LCS}}(X_{i},Y_{j-1})$, და ${\mathit {LCS}}(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