algorithm - प्रत्यय वृक्ष का उपयोग करते हुए एक स्ट्रिंग में सबसे लंबा ताल




palindrome suffix-tree (4)

मैं एक स्ट्रिंग में सबसे लंबे तालमेल को खोजने की कोशिश कर रहा था। ब्रूट बल समाधान O (n ^ 3) समय लेता है। मैंने पढ़ा कि प्रत्यय के पेड़ों का उपयोग करके इसके लिए एक रैखिक समय एल्गोरिथ्म है। मैं प्रत्यय पेड़ों से परिचित हूं और उन्हें बनाने में सहज हूं। आप सबसे लंबे ताल का पता लगाने के लिए निर्मित प्रत्यय वृक्ष का उपयोग कैसे करते हैं।


डीपी समाधान:

int longestPalin(char *str)
{
    n = strlen(str);
    bool table[n][n]l
    memset(table, 0, sizeof(table));
    int start = 0;

    for(int i=0; i<n; ++i)
        table[i][i] = true;
    int maxlen = 1;

    for(int i=0; i<n-1; ++i)
    {
        if(str[i] == str[i+1])
        {
            table[i][i] = true;
            start = i;
            maxlen = 2;
        }
    }

    for(int k=3; k<=n; ++k)
    {
        for(int i=0; i<n-k+1; ++i)
        {
            int j = n+k-1;
            if(str[i] == str[j] && table[i+1][j-1])
            {
                table[i][j] = true;
                if(k > maxlen)
                {
                    start = i;
                    maxlen = k;
                }
            }
        }
    }
    print(str, start, start+maxlen-1);
    return maxlen;
}

मेरा मानना ​​है कि आपको इस तरह आगे बढ़ने की जरूरत है:

Y 1 y 2 ... y n को अपनी स्ट्रिंग (जहां y मैं अक्षर हैं) होना चाहिए।

S f = y 1 y 2 ... y n $ और S r = y n y n - 1 ... y 1 # का सामान्यीकृत प्रत्यय वृक्ष बनाएं (अक्षरों को उल्टा करें और S f ($) के लिए अलग-अलग अंतिम वर्ण चुनें। और S r (#)) ... जहां S f का अर्थ "स्ट्रिंग, फॉरवर्ड" है और S r का अर्थ "स्ट्रिंग, रिवर्स" है

S f में प्रत्येक प्रत्यय i के लिए, S r में प्रत्यय n - i + 1 के साथ सबसे कम सामान्य पूर्वज लगाएं।

जड़ से क्या चलता है जब तक यह सबसे कम सामान्य पूर्वज एक palindrome है, क्योंकि अब सबसे कम सामान्य पूर्वज इन दो प्रत्ययों के सबसे लंबे सामान्य उपसर्ग का प्रतिनिधित्व करता है। याद करें कि:

(1) प्रत्यय का एक उपसर्ग एक विकल्प है।

(२) एक पलिंद्रा इसके विपरीत के समान एक तार है।

(३) तो एक तार के भीतर सबसे लंबा निहित पैलिंड्रोम इस स्ट्रिंग और इसके उलट का सबसे लंबा सामान्य प्रतिस्थापन है।

(४) इस प्रकार, एक स्ट्रिंग के भीतर सबसे लंबा निहित पैलिंड्रोम एक स्ट्रिंग और इसके विपरीत के बीच प्रत्यय के सभी जोड़े के सबसे लंबे सामान्य उपसर्ग है। यही हम यहां कर रहे हैं।

उदाहरण

केला शब्द लेते हैं।

= केले $

एस आर = आनब #

नीचे S f और S r का सामान्यीकृत प्रत्यय वृक्ष है, जहां प्रत्येक पथ के अंत में संख्या संबंधित प्रत्यय का सूचकांक है। एक छोटी सी गलती है, Blue_4 के माता-पिता की सभी 3 शाखाओं के लिए एक समान

पेड़ में सबसे कम आंतरिक नोड इस स्ट्रिंग और इसके रिवर्स का सबसे लंबा सामान्य विकल्प है। पेड़ में सभी आंतरिक नोड्स को देखते हुए आप इसलिए सबसे लंबे समय तक पैलिंड्रोम पाएंगे।

सबसे लंबा पलिंद्रा ग्रीन_0 और ब्लू_1 (यानी, केला और अनाना) के बीच पाया जाता है और अनाना है

संपादित करें

मुझे सिर्फ यह पेपर मिला है जो इस प्रश्न का उत्तर देता है।


Skiena - The Algorithm Design Manual से सरल और संक्षिप्त विवरण Skiena - The Algorithm Design Manual

S [प्रत्यय वृक्ष का उपयोग करके] सबसे लंबे तालमेल का पता लगाएं - एक पालिंद्रा एक स्ट्रिंग है जो वर्णों के क्रम को उलट जाती है, जैसे कि मैडम । एक स्ट्रिंग एस में सबसे लंबे पैलिंड्रोम को खोजने के लिए, एस के सभी प्रत्ययों और एस के उलट वाले एकल प्रत्यय वृक्ष का निर्माण करें, जिसके प्रत्येक पत्ती को इसकी शुरुआती स्थिति से पहचाना जाता है। इस पेड़ में किसी भी नोड द्वारा एक पैलिंड्रोम को परिभाषित किया गया है जो एक ही स्थिति से बच्चों को आगे और उलट देता है।


कुछ साल देर से ...

मान लें कि मूल स्ट्रिंग है, और r उलटा है। चलिए यह भी मान लेते हैं कि हमने पूरी तरह से s का उपयोग करके एक प्रत्यय ST बनाया है।

हमारा अगला कदम ST खिलाफ r सभी प्रत्ययों की जांच करना है। r प्रत्येक नए प्रत्यय के साथ, हम पेड़ में एक पूर्ववर्ती प्रत्यय के विरुद्ध सफलतापूर्वक मिलान किए गए k अक्षर (यानी, s के प्रत्ययों में से एक) को बनाए रखेंगे।

एक उदाहरण के रूप में, मान लीजिए कि हम r से प्रत्यय "RAT" का मिलान कर रहे हैं, और "RA" से शुरू होने वाले कुछ प्रत्ययों को समाहित करते हैं, लेकिन कोई भी "RAT" से मेल नहीं खाता है। k 2 के बराबर होगा जब हमें अंत में अंतिम पात्रों "T" के लिए आशा छोड़नी होगी। हमने r के प्रत्यय के पहले दो वर्णों का मिलान पहले दो वर्णों के प्रत्यय के साथ किया। हम इस नोड को कॉल करेंगे कि हम n पहुंच गए।

अब, हमें कैसे पता चलेगा कि हमने एक पालिंद्रा पाया है? n तहत सभी पत्ती नोड्स की जांच करके।

एक पारंपरिक प्रत्यय वृक्ष में, प्रत्येक प्रत्यय का प्रारंभिक सूचकांक उस प्रत्यय शाखा के पत्ती नोड पर संग्रहीत होता है। हमारे उपरोक्त उदाहरण में, s "RA" से शुरू होने वाले प्रत्ययों का एक समूह हो सकता है, जिनमें से प्रत्येक n के पत्ती नोड वंशज में मौजूद अनुक्रमित में से एक पर शुरू होता है।

आइए इन सूचकांकों का उपयोग करें।

इसका क्या मतलब है अगर हम एस k वर्णों के विरूद्ध R के सबस्ट्रिंग में से किसी एक के k अक्षर से मेल खाते हैं। खैर, इसका सीधा सा मतलब है कि हमने कुछ स्ट्रिंग उलट पाए। लेकिन इसका क्या मतलब है अगर एस जहां स्थान R में शुरू होता है वह S प्लस के में मिलान किए गए प्रतिस्थापन के बराबर है? हां, इसका मतलब है कि s[i] through s[i+k] वही पढ़ता है जो s[i+k] through s[i] ! और इसलिए, परिभाषा हो कि हमने आकार k का एक palindrome स्थित किया है।

अब, आपको बस इतना करना है कि अब तक पाए गए सबसे लंबे ताल पर एक टैब रखें, और इसे अपने फ़ंक्शन के अंत में वापस कर दें।





suffix-tree