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

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

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

== სირთულე ==
ეს ამოცანა არის NP-რთული ამოცანა. ის დინამიური პროგრამირების პრინციპით პოლინომიურ დროში იხსნება.<ref>{{cite journal| author = David Maier| title = The Complexity of Some Problems on Subsequences and Supersequences| journal = J. ACM| volume = 25| year = 1978| pages = 322&ndash;336| doi = 10.1145/322063.322075| publisher = ACM Press| issue = 2}}</ref>  

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

: <math>O\left( 2^{n_1} \sum_{i>1} n_i\right).</math>

n და m სიგრძის ორი მიმდევრობისთვის დროის სირთულე დინამიური პროგრამირებით იქნება [[ასიმპტოტური აღნიშვნა O-დიდი|O]](n × m).<ref>{{cite journal |last1=Wagner |first1=Robert |last2=Fischer |first2=Michael |date=January 1974 |title=The string-to-string correction problem |url=http://www.inrg.csie.ntu.edu.tw/algorithm2014/homework/Wagner-74.pdf |journal=Journal of the ACM |volume=21 |issue=1 |pages=168–173 |doi=10.1145/321796.321811 |access-date=2018-05-03 }}</ref> ნებისმიერი რაოდენობის ქვემიმდევრობისთვის დინამიური პროგრამირების ამოხსნის დროის სირთულე იქნება  

: <math>O\left(N \prod_{i=1}^{N} n_i\right).</math>

== ამოხსნა ორი მიმდევრობისთვის ==
{{წყარო}}
=== LCS ფუნქცია ===
განვსაზღვროთ ორი მიმდევრობა შემდეგნაირად: <math>X=(x_1 x_2 \cdots x_m)</math> და <math>Y=(y_1 y_2 \cdots y_n)</math> . <math>X</math>-ის პრეფიქსები არიან <math>X_{1,2,\dots,m}</math> ; <math>Y</math>-ის კი  <math>Y_{1,2,\dots,n}</math> .<math>\mathit{LCS}(X_i,Y_j)</math> -ით აღვნიშნოთ უგრძესი საერთო ქვემიმდევრობა პრეფიქსებისთვის <math>X_i</math> და <math>Y_j</math> .   

:<math>
\mathit{LCS}(X_i,Y_j)=\begin{cases}
 \empty & \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\ne y_j.
\end{cases}
</math>

რათა ვიპოვოთ LCS <math>X_i</math> და <math>Y_j</math>-თვის, შევადაროთ  <math>x_i</math> და <math>y_j</math>. თუ ისინი ტოლია, მაშინ ქვემიმდევრობა <math>\mathit{LCS}(X_{i-1},Y_{j-1})</math> -ზე ერთით მეტი იქნება . თუ ისინი ტოლი არ არიან, მაშინ  <math>\mathit{LCS}(X_i,Y_{j-1})</math>, და <math>\mathit{LCS}(X_{i-1},Y_j)</math> შორის უგრძესის ტოლი გახდება.

==იმპლემენტაცია C++-ზე==
<source lang="cpp">
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];
}
</source>
==რესურსები ინტერნეტში==
* [http://xlinux.nist.gov/dads/HTML/longestCommonSubsequence.html Dictionary of Algorithms and Data Structures: longest common subsequence]
* [http://rosettacode.org/wiki/Longest_common_subsequence A collection of implementations of the longest common subsequence in many programming languages]
* [http://www.codingalpha.com/longest-common-subsequence-c-program/ Implementation of Longest Common Subsequence Algorithm in C Programming Language]

==სქოლიო==
{{სქოლიო}}

[[კატეგორია:კომბინატორიკა]]
[[კატეგორია:პროგრამირება]]
[[კატეგორია:ალგორითმები]]