सबसे लंबा आम पालिंड्रोमिक परिणाम

Question

क्या कोई कुशल एल्गोरिदम है जो दो दिए गए तारों के सबसे लंबे समय तक सामान्य पालिंड्रोमिक उपक्रम की लंबाई की गणना करता है?

उदाहरण के लिए

:

स्ट्रिंग 1. afbcdfca

स्ट्रिंग 2. bcadfcgyfka

LCPS 5 और LCPS स्ट्रिंग afcfa है।

Answer 1

हां।

बस के लिए एलसीएस के लिए दो अनुक्रमों से अधिक के लिए एल्गोरिदम का उपयोग करें।

अगर मैं गलत नहीं हूँ, तो

LCS(afbcdfca, acfdcbfa, bcadfcgyfka, akfygcfdacb) = afcfa 

यह तार यह पता लगाने की # 2 और # आप पर निर्भर है 4।

अद्यतन: नहीं, यहां एक काउंटररेक्स नमूना है: एलसीएस (अब, अबा, बाब, बाब) = एबी, बीए। एलसीएस यह सुनिश्चित नहीं करता है कि बाद में एक पालिंड्रोम होगा, आपको शायद इस बाधा को जोड़ने की जरूरत है। वैसे भी, एलसीएस के लिए पुनरावृत्ति समीकरण एक अच्छा प्रारंभिक बिंदु है।

यदि आप जेनरेटर शैली में एलसीएस लागू करते हैं, तो यह लंबाई एल के सभी एलसीएस उत्पन्न करता है, फिर एन -1, एन -2 आदि, तो आप एलसीएस- में सबसे लंबे आम सदस्य की काफी कुशलतापूर्वक गणना करने में सक्षम होना चाहिए। जेन (स्ट्रिंग 1, रिवर्स-स्ट्रिंग 1), एलसीएस-जेन (स्ट्रिंग 2, रिवर्स-स्ट्रिंग 2)। लेकिन अगर मैंने अत्यधिक कुशल एलसीएस-जीन है तो मैंने अभी तक जांच नहीं की है।

Answer 2

यह इस समस्या के रूप में ही है: नीचे मैं तुम्हें एक सीडी (रों) विधि (जो एक चार dict जिससे आपको पता चलता रिटर्न दे http://code.google.com/codejam/contest/1781488/dashboard#s=p2

http://code.google.com/codejam/contest/1781488/dashboard#s=a&a=2

कोड में जहां अगले या पिछले चार स्ट्रिंग में वह char के बराबर है)। एक गतिशील प्रोग्रामिंग समाधान को लागू करने के लिए इसका उपयोग करें जिसके लिए मैंने आपको नमूना कोड भी दिया है।

गतिशील प्रोग्रामिंग के साथ केवल लेन (एस 1) * लेन (एस 1)/2 राज्य हैं इसलिए ऑर्डर (एन^2) संभव है।

विचार या तो एस 1 से चार लेना है या इसे नहीं लेना है। यदि आप एस 1 को बंद करते हैं, तो आपको इसे आगे और पीछे (एस 1 और एस 2 दोनों) से ले जाना चाहिए। यदि आप इसे नहीं लेते हैं, तो आप आगे बढ़ते हैं 1. (इसका मतलब है कि एस 2 की स्थिति एस 1 की स्थिति के साथ समन्वयित होती है क्योंकि आप हमेशा दोनों के बाहर से लालची लेते हैं - इसलिए आप केवल चिंता करते हैं कि एस 1 के कितने राज्य हो सकते हैं)।

यह कोड आपको सबसे अधिक तरीके से प्राप्त करता है। सीडी 1 (चार ताना 1) आपको अगले चरित्र को उस चार्ट के बराबर एस 1 में ढूंढने में मदद करता है जो आप हैं (आगे और पीछे दोनों)।

पुनरावर्ती हल() विधि में आपको यह तय करने की आवश्यकता है कि start1, end1 .. आदि होना चाहिए। 2 कुल में जोड़े हर बार जब आप एक चरित्र ले -

s1 = "afbcdfca" 
s2 = "bcadfcgyfka" 

def cd(s): 
    """returns dictionary d where d[i] = j where j is the next occurrence of character i""" 
    char_dict = {} 
    last_pos = {} 
    for i, char in enumerate(s): 
     if char in char_dict: 
      _, forward, backward = char_dict[char] 
      pos = last_pos[char] 
      forward[pos] = i 
      backward[i] = pos 
      last_pos[char] = i 
     else: 
      first, forward, backward = i, {}, {} 
      char_dict[char] = (first, forward, backward) 
      last_pos[char] = i 
    return char_dict 

print cd(s1) 
"""{'a': ({0: 7}, {7: 0}), 'c': ({3: 6}, {6: 3}), 'b': ({}, {}), 'd': ({}, {}), 'f': ({1: 5}, {5: 1})}""" 

cd1, cd2 = cd(s1), cd(s2) 

cache = {} 
def solve(start1, end1, start2, end2): 
    state = (start1, end1) 
    answer = cache.get(state, None) 
    if answer: 
     return answer 

    if start1 < end1: 
     return 0 
    c1s, c1e = s1[start1], s1[end1] 
    c2s, c2e = s2[start2], s2[end2] 

    #if any of c1s, c1e, c2s, c2e are equal and you don't take, you must 
    #skip over those characters too: 
    dont_take_end1 = solve(start1, end1 - 1, start2, end2) 

    do_take_end1 = 2 
    if do_take_end1: 
     end1_char = s1[end1] 
     #start1 = next character along from start1 that equals end1_char 
     #end1 = next char before end1 that equals end1_char 
     #end2 = next char before end2 that.. 
     #start2 = next char after .. that .. 
     do_take_end1 += solve(start1, end1, start2, end2) 


    answer = cache[state] = max(dont_take_end1, do_take_end1) 
    return answer 

print solve(0, len(s1), 0, len(s2)) 

Answer 3

यहाँ लाइन द्वारा मेरी सरल पूर्वाभ्यास लाइन है (जब तक start1 == END1 तो 1 जोड़) के बाद से यह काफी आम है और समय लोगों की सबसे गतिशील समझाने प्रोग्रामिंग भाग 70% और गोर विवरण पर रुकें।

1) इष्टतम बुनियाद: X[0..n-1] n लंबाई और L(0, n-1) के इनपुट अनुक्रम हो X[0..n-1].

की सबसे लंबी मुरजबंध संबंधी किसी परिणाम की लंबाई होना एक्स के अंतिम और प्रथम वर्ण ही, L(0, n-1) = L(1, n-2) + 2 कर रहे हैं तो करते हैं। प्रतीक्षा करें, क्या होगा यदि दूसरा और दूसरा अंतिम अक्षर समान नहीं है, तो आखिरी और पहले बिंग यह बेकार नहीं होगा। इस "अनुवर्ती" को निरंतर नहीं होना चाहिए।

/* Driver program to test above functions */ 
int main() 
{ 
    char seq[] = "panamamanap"; 
    int n = strlen(seq); 
    printf ("The lnegth of the LPS is %d", lps(seq, 0, n-1)); 
    getchar(); 
    return 0; 
} 

int lps(char *seq, int i, int j) 
{ 
    // Base Case 1: If there is only 1 character 
    if (i == j)  
     return 1;  

    // Base Case 2: If there are only 2 characters and both are same 
    if (seq[i] == seq[j] && i + 1 == j)  
     return 2;  

    // If the first and last characters match 
    if (seq[i] == seq[j])  
     return lps (seq, i+1, j-1) + 2;  

    // If the first and last characters do not match 
    else return max(lps(seq, i, j-1), lps(seq, i+1, j)); 
} 

ऊपर कार्यान्वयन को देखते हुए, निम्नलिखित सभी विभिन्न पात्रों के साथ लंबाई 6 के एक दृश्य के लिए एक आंशिक प्रत्यावर्तन का पेड़ है।

   L(0, 5) 
      /  \ 
      /  \ 
     L(1,5)   L(0,4) 
    / \   / \ 
    / \  / \ 
    L(2,5) L(1,4) L(1,4) L(0,3) 

ऊपर आंशिक प्रत्यावर्तन ट्री में L(1, 4) दो बार हल की जा रही है। यदि हम पूर्ण रिकर्सन पेड़ खींचते हैं, तो हम देख सकते हैं कि कई उपप्रणाली हैं जिन्हें बार-बार हल किया जाता है। अन्य सामान्य गतिशील प्रोग्रामिंग (डीपी) समस्याओं की तरह, उसी सबप्रोबलेम्स के पुनर्मूल्यांकन को अस्थायी सरणी L[][] को नीचे के तरीके से बनाकर टाला जा सकता है।

// seq

int lps(char *str) 
{ 
    int n = strlen(str); 
    int i, j, cl; 
    int L[n][n]; // Create a table to store results of subproblems 


    // Strings of length 1 are palindrome of length 1 
    for (i = 0; i < n; i++) 
     L[i][i] = 1; 

    for (cl=2; cl<=n; cl++)        //again this is the length of chain we are considering 
    { 
     for (i=0; i<n-cl+1; i++)       //start at i 
     { 
      j = i+cl-1;         //end at j 
      if (str[i] == str[j] && cl == 2)    //if only 2 characters and they are the same then set L[i][j] = 2 
       L[i][j] = 2; 
      else if (str[i] == str[j])     //if greater than length 2 and first and last characters match, add 2 to the calculated value of the center stripped of both ends 
       L[i][j] = L[i+1][j-1] + 2; 
      else 
       L[i][j] = max(L[i][j-1], L[i+1][j]);  //if not match, then take max of 2 possibilities 
     } 
    } 

    return L[0][n-1]; 
} 

में सबसे लंबे समय तक मुरजबंध संबंधी किसी परिणाम की लंबाई देता है तो यह सिर्फ गैर गतिशील प्रोग्रामिंग की तरह तार्किक है, यह सिर्फ यहाँ है हम एक सरणी में परिणाम को बचाने इसलिए हम गणना नहीं है