दी गई लंबाई के सामान्य अनुक्रम

Question

सभी को दो स्ट्रिंग्स की लंबाई k के सामान्य अनुक्रमों के अच्छे तरीके क्या हैं?

उदाहरण:

s1 = AAGACC

s2 = AGATAACCAGGAGCTGC

लंबाई 5 के सभी आम subsequences: AAGACAAACCAGACCAAGCC

Answer 1

सभी का एक trie बनाएं kkसे पर जाएं और यदि यह त्रिभुज में है तो k की प्रत्येक अनुक्रम की जांच करें।

Answer 2

एलसीएस मैट्रिक्स से अनुक्रमों का पुनर्निर्माण करना एक अपेक्षाकृत सरल तरीका होगा। ऐसा करने के लिए यहां एक ओ (एन^2 * के + एक्स * एन) एल्गोरिदम है, जहां x आउटपुट का आकार है (यानी लंबाई के के सामान्य अनुवर्ती संख्याओं की संख्या)। यह सी ++ में है, लेकिन यह सेल्सियस के लिए अनुवाद करने के लिए नहीं बल्कि आसान होना चाहिए:

const int N = 100; 
int lcs[N][N]; 
set<tuple<string,int,int,int>> vis; 

string s1 = "AAGACC"; 
string s2 = "AGATAACCAGGAGCTGC"; 

void reconstruct(const string& res, int i, int j, int k) { 
    tuple<string,int,int,int> st(res, i, j, k); 
    if (vis.count(st)) 
     return; 
    vis.insert(st); 
    if (lcs[i][j] < k) return; 
    if (i == 0 && j == 0 && k == 0) { 
     cout << res << endl; 
     return; 
    } 
    if (i > 0) 
     reconstruct(res, i-1, j, k); 
    if (j > 0) 
     reconstruct(res, i, j-1, k); 
    if (i>0 && j>0 && s1[i-1] == s2[j-1]) 
     reconstruct(string(1,s1[i-1]) + res, i-1, j-1, k-1); 
} 

int main() { 
    lcs[0][0] = 0; 
    for (int i = 0; i <= s1.size(); ++i) 
     lcs[i][0] = 0; 
    for (int j = 0; j <= s1.size(); ++j) 
     lcs[0][j] = 0; 
    for (int i = 0; i <= s1.size(); ++i) { 
     for (int j = 0; j <= s2.size(); ++j) { 
      if (i > 0) 
       lcs[i][j] = max(lcs[i][j], lcs[i-1][j]); 
      if (j > 0) 
       lcs[i][j] = max(lcs[i][j], lcs[i][j-1]); 
      if (i > 0 && j > 0 && s1[i-1] == s2[j-1]) 
       lcs[i][j] = max(lcs[i][j], lcs[i-1][j-1] + 1); 
     } 
    } 
    reconstruct("", s1.size(), s2.size(), 5); 
} 

वहाँ भी एक O (n * (k + x)) इस हल करने के लिए जिस तरह से, एक अलग डीपी दृष्टिकोण के आधार पर किया जाना चाहिए: f (i, k) न्यूनतम अनुक्रमणिका j जैसे एलसीएस (i, j)> = k हो। हम पुनरावृत्ति

f(i, 0) = 0 for all i 
f(i, k) = min{f(i-1, k), 
       minimum j > f(i-1, k-1) such that s2[j] = s1[i]} 

हम भी मैट्रिक्स से लंबाई कश्मीर के दृश्यों को फिर से संगठित कर सकते हैं च है।

Answer 3

यहां एल्गोरिदम का एक संस्करण है जो रिकर्सन का उपयोग करता है, आकार k का एक ढेर और इसमें पहले से देखे गए वर्णों को छोड़ने के लिए दो अनुकूलन शामिल हैं और उप-अनुवर्ती मौजूद नहीं हैं जो मौजूद नहीं हैं। तार अद्वितीय नहीं हैं (डुप्लिकेट हो सकते हैं), इसलिए uniq के माध्यम से आउटपुट चलाएं।

#include <stdio.h> 
#include <string.h> 

/* s1 is the full first string, s2 is the suffix of the second string 
* (starting after the subsequence at depth r), 
* pos is the positions of chars in s1, r is the recursion depth, 
* and k is the length of subsequences that we are trying to match 
*/ 
void recur(char *s1, char *s2, size_t pos[], size_t r, size_t k) 
{ 
    char seen[256] = {0};  /* have we seen a character in s1 before? */ 
    size_t p0 = (r == 0) ? 0 : pos[r-1] + 1; /* start at 0 or pos[r-1]+1 */ 
    size_t p1 = strlen(s1) - k + r;    /* stop at end of string - k + r */ 
    size_t p; 

    if (r == k)   /* we made it, print the matching string */ 
    { 
     for (p=0; p<k; p++) 
      putchar(s1[pos[p]]); 
     putchar('\n'); 
     return; 
    } 

    for (p=p0; p<=p1; p++)  /* at this pos[], loop through chars to end of string */ 
    { 
     char c = s1[p];   /* get the next char in s1 */ 
     if (seen[c]) 
      continue;   /* don't go any further if we've seen this char already */ 
     seen[c] = 1; 

     pos[r] = p; 
     char *s = strchr(s2, c);  /* is this char in s2 */ 
     if (s != NULL) 
      recur(s1, s+1, pos, r+1, k);  /* recursively proceed with next char */ 
    } 
} 


int main() 
{ 
    char *s1 = "AAGACC"; 
    char *s2 = "AGATAACCAGGAGCTGC"; 
    size_t k = 5; 
    size_t pos[k]; 

    if (strlen(s1) < k || strlen(s2) < k)  /* make sure we have at least k chars in each string */ 
     return 1;  /* exit with error */ 

    recur(s1, s2, pos, 0, k); 
    return 0; 
} 

उत्पादन होता है:

AAGAC 
AAGCC 
AAACC 
AGACC