1044. Longest Duplicate Substring

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is "".

 

Example 1:

Input: s = "banana"
Output: "ana"

Example 2:

Input: s = "abcd"
Output: ""

 

Constraints:

  • 2 <= s.length <= 3 * 104
  • s consists of lowercase English letters.

Rust Solution

struct Solution;

use std::collections::HashMap;

const MOD: u64 = 1_000_000_007;
const P: u64 = 26;

impl Solution {
    fn longest_dup_substring(s: String) -> String {
        let mut lo = 0;
        let mut hi = s.len();
        let mut res = "".to_string();
        let s: Vec<char> = s.chars().collect();
        let n = s.len();
        while lo < hi {
            let mid = (lo + hi + 1) / 2;
            if let Some(s) = Self::exist(mid, &s, n) {
                res = s;
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        res
    }

    fn exist(size: usize, s: &[char], n: usize) -> Option<String> {
        let mut pos: HashMap<u64, usize> = HashMap::new();
        let mut hash: u64 = 0;
        let mut pn: u64 = 1;
        for i in 0..size {
            hash *= P;
            hash += (s[i] as u8 - b'a') as u64;
            hash %= MOD;
            pn *= P;
            pn %= MOD;
        }
        pos.insert(hash, size);
        for i in size..n {
            hash *= P;
            hash += (s[i] as u8 - b'a') as u64;
            hash += MOD;
            hash -= (pn * (s[i - size] as u8 - b'a') as u64) % MOD;
            hash %= MOD;
            if let Some(end) = pos.insert(hash, i + 1) {
                if s[end - size..end] == s[i + 1 - size..=i] {
                    return Some(s[i + 1 - size..=i].iter().copied().collect::<String>());
                }
            }
        }
        None
    }
}

#[test]
fn test() {
    let s = "banana".to_string();
    let res = "ana".to_string();
    assert_eq!(Solution::longest_dup_substring(s), res);
    let s = "abcd".to_string();
    let res = "".to_string();
    assert_eq!(Solution::longest_dup_substring(s), res);
    let s = "ababdaebdabedeabbdddbcebaccececbccccebbcaaabaadcadccddaedaacaeddddeceedeaabbbbcbacdaeeebaabdabdbaebadcbdebaaeddcadebedeabbbcbeadbaacdebceebceeccddbeacdcecbcdbceedaeebdaeeabccccbcccbceabedaedaacdbbdbadcdbdddddcdebbcdbcabbebbeabbdccccbaaccbbcecacaebebecdcdcecdeaccccccdbbdebaaaaaaeaaeecdecedcbabedbabdedbaebeedcecebabedbceecacbdecabcebdcbecedccaeaaadbababdccedebeccecaddeabaebbeeccabeddedbeaadbcdceddceccecddbdbeeddabeddadaaaadbeedbeeeaaaeaadaebdacbdcaaabbacacccddbeaacebeeaabaadcabdbaadeaccaecbeaaabccddabbeacdecadebaecccbabeaceccaaeddedcaecddaacebcaecebebebadaceadcaccdeebbcdebcedaeaedacbeecceeebbdbdbaadeeecabdebbaaebdddeeddabcbaaebeabbbcaaeecddecbbbebecdbbbaecceeaabeeedcdecdcaeacabdcbcedcbbcaeeebaabdbaadcebbccbedbabeaddaecdbdbdccceeccaccbdcdadcccceebdabccaebcddaeeecddddacdbdbeebdabecdaeaadbadbebecbcacbbceeabbceecaabdcabebbcdecedbacbcccddcecccecbacddbeddbbbadcbdadbecceebddeacbeeabcdbbaabeabdbbbcaeeadddaeccbcdabceeabaacbeacdcbdceebeaebcceeebdcdcbeaaeeeadabbecdbadbebbecdceaeeecaaaedeceaddedbedbedbddbcbabeadddeccdaadaaeaeeadebbeabcabbdebabeedeeeccadcddaebbedadcdaebabbecedebadbdeacecdcaebcbdababcecaecbcbcdadacaebdedecaadbaaeeebcbeeedaaebbabbeeadadbacdedcbabdaabddccedbeacbecbcccdeaeeabcaeccdaaaddcdecadddabcaedccbdbbccecacbcdecbdcdcbabbeaacddaeeaabccebaaaebacebdcdcbbbdabadeebbdccabcacaacccccbadbdebecdaccabbecdabdbdaebeeadaeecbadedaebcaedeedcaacabaccbbdaccedaedddacbbbdbcaeedbcbecccdbdeddcdadacccdbcdccebdebeaeacecaaadccbbaaddbeebcbadceaebeccecabdadccddbbcbaebeaeadacaebcbbbdbcdaeadbcbdcedebabbaababaacedcbcbceaaabadbdcddadecdcebeeabaadceecaeccdeeabdbabebdcedceaeddaecedcdbccbbedbeecabaecdbba".to_string();
    let res = "aeeebaabd".to_string();
    assert_eq!(Solution::longest_dup_substring(s), res);
    let s = "shabhlesyffuflsdxvvvoiqfjacpacgoucvrlshauspzdrmdfsvzinwdfmwrapbzuyrlvulpalqltqshaskpsoiispneszlcgzvygeltuctslqtzeyrkfeyohutbpufxigoeagvrfgkpefythszpzpxjwgklrdbypyarepdeskotoolwnmeibkqpiuvktejvbejgjptzfjpfbjgkorvgzipnjazzvpsjxjscekiqlcqeawsdydpsuqewszlpkgkrtlwxgozdqvyynlcxgnskjjmdhabqxbnnbflsscammppnlwyzycidzbhllvfvheujhnxrfujwmhwiamqplygaujruuptfdjmdqdndyzrmowhctnvxryxtvzzecmeqdfppsjczqtyxlvqwafjozrtnbvshvxshpetqijlzwgevdpwdkycmpsehxtwzxcpzwyxmpawwrddvcbgbgyrldmbeignsotjhgajqhgrttwjesrzxhvtetifyxwiyydzxdqvokkvfbrfihslgmvqrvvqfptdqhqnzujeiilfyxuehhvwamdkkvfllvdjsldijzkjvloojspdbnslxunkujnfbacgcuaiohdytbnqlqmhavajcldohdiirxfahbrgmqerkcrbqidstemvngasvxzdjjqkwixdlkkrewaszqnyiulnwaxfdbyianmcaaoxiyrshxumtggkcrydngowfjijxqczvnvpkiijksvridusfeasawkndjpsxwxaoiydusqwkaqrjgkkzhkpvlbuqbzvpewzodmxkzetnlttdypdxrqgcpmqcsgohyrsrlqctgxzlummuobadnpbxjndtofuihfjedkzakhvixkejjxffbktghzudqmarvmhmthjhqbxwnoexqrovxolfkxdizsdslenejkypyzteigpzjpzkdqfkqtsbbpnlmcjcveartpmmzwtpumbwhcgihjkdjdwlfhfopibwjjsikyqawyvnbfbfaikycrawcbkdhnbwnhyxnddxxctwlywjcisgqfsctzatdgqqauuvgclicdrpjcphysqdjaflpdbmvnhqggixxzcmpsysbwfkzwxzjictnngufpqhcxlbkodyrqlfomlkiefbmcfenugzqnyqqvgpxonmizkpjdlaqyyowjagzkzrzvcrupfyofeftyfvoqorzvxphhdhydnqiyiczfcgzsecxzsoaobwrixcajabjnvtoerzwayjowahrmuixmmkbtchogfizmvbjnpespxngxjxntohzatlpkcmpphmewevpteharnszafbpbexrvnbedieojezdhnyooiivhnhakilvkobxepbksnqrtxxuqhalvtjspyvporalbliiwjciamlhttaydhxoelimuorjnfvebjhcocbkrgbguwdncodskzzoqrzgavsbjcippetltqaxjhkqacwlgmsbxezqubyzeznnsoqegkykzlxohvitbmjcxllbrvgdijyovpjyeaojlyxqwnheyblznwoyikhqiutotpfukyqkvatxotulvlqzfcvskdccuixthzqrwymzccosjmjqjigehcnfphjuuybaxxukconatzseljyirycbhucxmwwftulfwfmyqyprlnsmxzyfmgjctgeunuuexhbrbsaaingqxqrjvpuhbvcmyztmkgenhonajrkzfrqjinjrbmjyinhwvlcmmxvbgvjgfmaoliosmxbonvlzoiqvkxxtoposygcgkcotohcrauivxxvmrghuauadwojxjligrgstczirnvhqpzwgjbvqzlkxltqnqrfxieggnuriytavbnouwhuamdtlspednyckixkhxedjmotiuucewllthhducwgwmgzxsbkqzfnqfynwisvsctyqdoaiypjivtxkxgoyhwhccklbdjoqykaqzljejlizgbehekmkfetvgfstmypmfnyoundudqlorcogbzoznddfalthwpmiewkmvogmzirbprjftbtffjrkrfminnechitfyfaujgtugadqbrskulsjbaunonxolauvsifevpdyurvfocxtkizflcuvltzuhwyhlbxaphifhtgkfktfnnmocpenrlujsuppbbuorvtubuiyszawzftijwhwgdyubjmmodzybiyunksuixnkariubegpdgctbayaynfskkuyhjvegsjwsbppodvhpjdjlzhxixswdncapxyfjspxeqxdfkhockvrzoisikaymoiqzqbjyoscwegfomlnurwboesfiszetebjblaolnovgvfcpnbemwambkhwcgdbhvkoluhjfxlfrfaeedocdilaboesauplmttewlbojkocklhsbzrtzeyhqtmgroupbzlymupmupsvlkzchclujuozzmngjvktzstsvocxrziuxelruwojzaleyrkjkdleavwqxwgjdbtiywqtdtaamrlcjogxufhgvoqpqkgopbtyqchzhexqgecheahjzxapqjdylzjqhzlzssbjmokncxalgasexztnlzfisxxpeerywlrjdohprewwnlwdbtwmfnnxnoolfhqqxzcvoymdbvmaoliedpvwzyvgyrwjguvoqnxrnaeqwvcfrqkwjmlvxovptultyfuxerelpfgctnpdxluqeruxkxqntosggfjqmrnlnkhhilznpycdrnemnktcsmzufpqgiraphzmgfhevzejhavsypohpttnnowfahpxfwmvxgwfuomxemdkzdlzldesmowzmhwoydnsovwykxqyllbmcurlvtwcfwxvvkxfknwwcwfjkzjtonalgijdsulcfagehiptszrcltbbypopdbmdfkyofelmrdmdbceguyxnkheqqtbletpqmjugpckmjyuuvsbqhyzmposwcgscnishluuhnwkyrkujefpgtsqrmcoortgitpdoagdncxlofkqozgngbtmlyyoyodcmcwetdtltupjrtemrjswekkfjvfecmvagyptjjuwsqpjwlxxosqhpssdvjraaicjfwvesyqfbumjjbqytkinpldxopxjzmvpigmberobyzyxwvwmlmbziduqhmbescgkvhgqtalmaxfsjlysmvrizgvrudstiwmaahtqehfbofvqwgqygvseykmgmhgjbxcrtdjqvojvyhohallyewqelzhjeuqmmsqhkluvqsfmxzbqqokehfoqrlqmwpnwojfowqpqebnuggeuvsszgfywceolvabyvbrwatuyherijsdqvpyyhdyradbammmchqkvdbxpbrxzrpfrsiiezvowrfqejibvociujtcwbygvfwojgfnvvwqlqqgipxhrogppzghtnweodaxuqxknnqnajlnsvheiycsvifvoljsncgnunsqcymnyoeeslrjflpprvtksimffvnuvakskdakvmlkpowfpfzdrcfctikhvvbagrvjlzjydnlmspzyynyjjfxnozpjjgjelipswsmfroitqphzsuqgumlnkxksbzhrsvcnfwufofhurmhksvvfjzggbtgrezkrkqmhduyqgwuwxoxaiifemtwrbilftiuhcgpjvqxldrnlzphdffncevlcyrxlpbwuswjfdegexeoooshdfqtqithpfocyowaqeedikssptyvkabhtaeotcwxccgguuotqvypugpcbwzalxwqbjdcokoxjnqhggpbbfeyjiellsikiqqtxpvzmjsfleepjpbxpeicxfcwbpprzgcrjgjaxshewradetsqsvfmcxptmksecfpynqzpctqpogcgokzrkltsbmwxkmynasohpkzjupapngusnvdjfqezqhyikllgkelewwwhhbdjvxdagnnxscjkotbbmhzkqbjwuwidrnvmztikmqjcxmcpgkoudhydmdvberfuvjnhlnfcsbpzmuquvrgogtfwefhqzkmxxgadtvjpxvurxprbsssihviypclwkjfaatzjxtvlzwaacqlwnqetgkldqaqghuihrgxbbpmjfsvaigqrhiiskkfibaeilqptkdsqqfwxeixuxgkiboaqnuaeutjcydnxyxnmattjrrxmthwvyipgazaxgrrjcvdnyxpktsldhluhicyqprxhljyfhawuvoonrwyklcdlmdvsgqrwqqomisksftsfyeifmupvylkjbagzyctuifbsrugqsbrkvskmundmczltpamhmgqespzgrkxebsvubrlmkwyqhjyljnkeqvdxtjxjvzlrubsiiahciwefwsswgssxmvyvgjrobvubcbgjomqajmotbcgqjudneovfbjtjzwqtsovzshmxeqofssukkvcdwlsdtyplrlgwtehnwvhhegtwkwnqqdiajpcaajsylesadaiflruewhrbrogbujbppunsqgytgnyuhnkejhccavaptbydtqhvyatftxcaaljyhhkkadzdhhzawgndunwwgknnbtqaddpszqgummmnomfqmdxqtwjexsbadfdqhnyixjslsaisscocbabivzokkgiinqqzsrtfpzjmxfkqmuzzlelqjtjidjarkwbwlcqrefokrlwdmuzyffdtajnqoimlzzpcgpjjwlqkusefzbgznhexzojxnzxmmedobgvdabtdoiskozrdrjscxwivaekrkyyfynuktmgyziteavdxfctvkfkrmsdwpaywzbkeojeycwdkectydojttisizruilwokhepscqdnjygiakomkhyujaffxjyxqmvkemqihpcdygprdeaxgjbkonfvgtzayfbmgwsskoyxjlknwwtehhhpjllhkcblyaxnbekoidbbyqvdqqsyfcemylmqskpxifcnhmemkkitqtbfwhmyemkzightkjbhlquticivpeeclpamsqoztxvdtcqbsonxyecnhcadtghkjckhrcdfggnqlwurydzbeybqkcfnnbwkciwaqdzgmcrbltvcuftxsqfpxnoombsbeoqxivgtkrjklxatgcorkdrvmngwlekeopgecefzxtprcoajoopxviijxilxfiwuajsbtcctfcqqgzhyjmonwdbyjlnneidyaqhhothzpzaxcthvbxpdcqofaeamxbqjwhunnqwclhcqhagawjsxygorgbuqryzickyplbaivkabbrkibqzqacabbwmnpndaqvbknbqcjuywxjrdbznndomwbbqfgulwczydrhrocebhygriiwxmwtjjyqqiqrjblxuamddlsiocdoysdaacuovljtpgocephnxuugdyggsnhcqiqhulyhlxiwzvhrtbmvjnhacwunckqzhpcthqgsupptdwkfeprbg".to_string();
    let res = "maoli".to_string();
    assert_eq!(Solution::longest_dup_substring(s), res);
    let s = "baaddcedaabeeebbddcdcdbaedcadbcbedddbbcbcbcdddbdddbdebecedabbdccdabbaaeedcbcacbcdebebaeeecaaddeceabbcaddabeceaceebedcabbcdcdbabdeeeacaceabaaaaeaeabbdecbdebedcedacbecccaeacbadecedbacbcdcebddebabbdddcdbbdccbdaccacaccbaabebcdbeadbdeebddbdddbabbeaeeabbdbcbcaaccdcabaebeadcaddeedcabebcbdbbbcdeeabbbadcbbadddadaddeacdbbbbecdadababacabcceaccdaddbcbbbccbdddacadcddddedeaeabebcdcaccceeecbdcaeebeabedbececeadbdcdcedadbbebedaaeacbedecddcabeddbadaaeceedbbedaadcbdebcbbbdcbeccaadeacdbebaedadadddbebccacecbcecdeeadaebbdbaeeaeebcadcbbedcdddacdeeaaeeeeebdccabbdaecdccaeacbecbdbadccaeeeeaceeabcacebebbccceadebeaeeeeceebaaaecbaccaccbccebeceaecdbbaacaadcecedddbcbacdaecbbddbaedbbbbbeacdeddaecbbdabebaaadceaabdedeadbbdbebbbcedbddaedccedcbebbdbbeaecdaabcdbadbbdbcdcbdeedbcbabebaaaeceebeccddcaaeebbedcdceeeebeaddcdabbcdbebdaabaedbeacccebbccbecaeeacbdaeeccdbdeadcdebbcddaeaebdacdadbecbacbaccdcaddbdcabadcdacadadbdbedadbecacecedccabbceeeeecaeccceedacbaeadacdcddccaeabbcecddddbbabaeeecedbaccabceecbbeedacbbcdddadccedbbcbcadccdddedeceaccdaeedcaebcdadbaededddbebaabdeebacabaaceabdeedabdacbeddadeaeedbddaccaacbababeeaeaecdbdaeabeeedbaeeddbcceecceebabbebebdedbaebbeebddeeccdabaeaecccbeeebacacdbecadabdcdeedeebccababdeeaccbdbbabdecdbdebabdbeeadacbccceebdeddebedbbbcbabdccbddeaceeccbecacdbbaecbbaabebadbbdbababddeccbcebcdbdbcebddaeaedeebacaaaecbdaabdedabcbedadcebbeadbcaadbcdbaeaacddeebcbebbdbecbcdebbcaaaacddebedabdaeeaeeaabbedcdabdceeaaddcbbeadccbcddceedcabbaecabadbadeabdbdcceaedcdbcdaeaebdbdbaacdeccedbaeeabbadaaaecceabceececaacecebabebbdebadeabdaadbbaebeeabebbdbeeccceccdbaceabbbeeecdccebdadeabbeddcdacdbeedbededbbedddabddeacbdbeeedcdeecaebcbabeecadccbedbeaadaebdcabedecdeacaccbeaadabddeadddccccbdcdecebeeceaadbaaabdedadbdccbdeabbdddebebcabbebaaabbbaccecebaecccaadecddbaabeebcabedebdabcbccaeadebabaacddecaccdacaadbbcdbdbdbeddedddebacaeadbaebaddedcebccdbbdcdbcaaaaccdaaceaebdadaceeeabedcacdddeeabecbacdcdbcebabccabecbbeeedbeeccabaeccccceaeaaceebcaacabbbcacdcebabdbcbaeeddaccdeadcbdedeabecdaecadbcbbdbcececbdbcdcbbbbdaacebccbaacbcaaeadbcbeeedaceebaeebadbbcceddbdaedabbdacdeadabeadccadbebcecbcdbaabbecddbaacaccbbbeaeadcebdccbaedaabdadcaebbdcdeaebeecdbbdbaadaedbeecccddacdedcdebbddaeecabebacaacdacdadcecdcaeaeaecbccedabbceebacdedceedeebbbacddacddedbaddaccaebeebeaadbeeeecdcaedadabddebcbcddccadaaadddbdbdccbdebbcededcdabbdbbdbbbedecadbdebebdedeebaadcaebebdececeaabbdaedeebbacecdbcbddeaaabdcbbdbabddabacbdebcbcccebdcccbcddcebdcbededbaadebebedcbebcccdddbabbeecbadcbeeeabbadddbbbcedcebbaabdeceecadaabdeaeabbebabbcedadbddcbedadcaededaedbeaaaeddadddabbeeaddddaaadedccddbcebeadcaebaaeabeeebecccbaddceebceeddabbdddcbeeadbecddebcebebeedcedbeabdbebcccdbbaadbabcbebadbecabbaeccbbeecaeebccdabbdcbadbdacbdccdccebeabceaaecbbeedeaacaddcedccaabaabeaecdadaceacacdcdcadabeacbeeabdcdaeceacdbdccccbbbaebcceaabcbecbabebcaebbbbdeaebbebaeeacbdbaddeaaeacedbdbaedecdbaecbbeddededbadbbadebabecdaadddbadeaabbeaebbaaeeacebcceabaaeabaecbdaeaccbedccceacdaceacceddaccdeddbaccbabdabdbcbeceaadcdaddbadeddbeceacbbebeacecccadcecacbecbacadbaaeaebbabceeddebbcbabbecbdbadcddddcebdabcadbbaeadbeadcceeccbacccbeccbdbaecbbdbeebbebbcbeccebccdcbbabcdaedbaaaaceeebddebdcebaecbadedaaccccabebdadbbcaceabbddeeeebcaebecaaaacaccaacddddcaedcdccbdabbbabbacdabedbbbaecccacadbacbcadabccedcababaedaceebcaccddeecdbcbbcdbbadbbbcccdcbdadbccaacbaeabbaecabccebcddbdbbbccbbcccdebbcabadcaeeecbacadaceeaecddeebeacadeabdabbbcdaeacdebddadbeeedbdbcebedbabbbebeaadabdabebaebaabdcbbceaececabecbdadeecccdebcbecaabbeccaedabbaaddeedaedbdbacdcaccbdbabbdebdebceceddbcddbabeebeecadcabbaedeabebdeeaaebaebaeaaaccbebceedadbcbbbaeceebcaedecbbebddccaadcadccbcababcadacbcabebcbbeecabbeecebeabceddaaeebdbdeeadeeebadbbcaaebcdcdeabaaecababaccaadcdebdeaddcaabaaaaedbadeddecdeaaecaedceabebdcceecdbcbcdaceeacececcadacaebadedebebcbcedcdbcadaddadbbadcebdeacceabaeedecbebbeccbabaaddddacccbddebbcbdedbebcccbbaecceeeccddacccaddecdcbaebdebbbccbdddeadaddacdcebebeedccddedddcbceadbbdddcabddbbbbdbabccbedcacabecabdeccdecebdbbcbdcdcaebbaceededeadcbccdbddbbebeeddbedaeadbdabebdcdbeecdaecbcecedcbeaceacdeebaadeeebaaeecdebeabadbbdbbcbeceebeeecdbdacebdcedbecccabdbaaacbeaecbddcaddbdeeeadeadedabacdeaadaedbdacccbbacadadedecddbcabcebdadeaecbeeaabacaddaeebcbdcabeacbddbecbbbbacbdbbdecebeedbeacdcabcdadcadcbbadaedaddabedbbbbabeddacedbaddcaececbdebeaeeceaecdedccbaadbdabdedbeccaeaddbaaabddbcabcbbbddbedbceddcdbcdbeeebbabbaedcdbdedaccacbddcdbaaadacdaabaeebdcedbdbedeeccaacbdcaaacbacccebcbadeececacbcaaaecccbabecedaebdaebdaecacaebceeddadecedbccdaababccadeeddbbdccecbddbbdacbeaabdaabebdaaebebcbacdccacebccaadaacaacbbaaaaadbdcebabddccebccebdbcbbebeadcbdcbaddcdaceedebdcdabaaeaeccdabadbdeacbaebcbcbadabadacdcebcdeaebddcabccddbababbadddaeaecbedcdeceebdaeebdbbdebabdaeeaedbcbdacdbbcbcaddeaaadcdbcdcacaabecbceabecbccaadaddaaeaccbbacceceddaedcebeccaaabcadaaddeacaebcdbbeeacbaaecddeadddcabbeebecdadbadceadecedccebbbcbdcbbceeedcbdcebaddabbdedceedeeaaabcbcecccadaebdcaeccabaaeebbbbaecbcbccbbacdadebcabbceeddcaebdccaeedcceeddecaaeebeeeadcacbacdaacbbbccdbdecbcaaceddaadacdcecbabdebdececeeecbedacddbaeaecbbcadeecbccccbcedcaddacdeecbaeaadeddcdcbabbabaeadecdcaaaaddbcddbabeeccbdbeaddbeceedbdbdcdcaabebcbacdbedbadbeecbbbdaabcceddcdabbdbdadbdcddeccbebdeaebbbaacceeddcbdadcacdaacebaeccdeacaddcbdbaeadcaaaceadcddeaaedadcadedaedacaaacabcdaaacecdbbabebebdeaadaecdcbbadeeecdbccedeebbddebecadcaeaeacacccecbadedaaeebddaeebbadcedaaadcdbcbcebabeccdddcbdaaadebeddbbdaeaceabecadcdecabdddbcedcdecceacbccbdbcaebbdbaabecedccaaceecbaabbebdeeaceedeadbaacdcebbbabdccaddcecedeebdeadebbacbcadbbcabccddeeccdcbdbcdacecaceddcdbaeececbdcaececdedabcaaaecdccebadedbdbbbdccececaeaebdacaddeacacddccdaccccadbecceaedacaacdabecdbbabecacabdebddcaadeeacccdbabebbbedadebaedeaaeeeaceaabdbccaabeabaaddbeaaadeabaddaabdcebdcebbedadacbeecddbcadbdccbabeeaecdebabdaabbcecdaebecebcaccadceeaaaaeeedbbaddeadacbccadbbeabeedacaddbaadabaebeaeeedbcbeeabebeeeedeaeadeccbbacadadbbceaacaecdcbbbaeacedbabcabddeacadcddaaaddabcccecbbcdaaeaccadbeaabbcdebcebdebdebabdbcdbdceadeccdabbeeaceebaadbdaadbcdeaeadbadcebeeabcbecaeaacbdceccbecadcceeabcabccadcddbdbcaabeadcdbbaeadacbbdddaedbccaadcceaacbaaaacbeaeaebdebdbdeaebcecaceeaebbebcadaadccbccdaedbbdbcceecacddeeadedbedaeddbaccddaecbeaadadcccabbeeabbecebdaacabedceadaebbbbccdccbabbeeebaaedcdecbaeaaaabdabebeacdcecaedbddbbccbcccceaedbeccdcdebaeaccbbdecaeeebcaebbdaacaedeebabecccdcaadecaeadeccedededeaeeddebedcdbeecedaaecdbacdddddeeebebacedabebbbeacbcddaeaeabbbcbcabdabcbdaedabbdbacedbebdcaeebecbacbeaceababecdcdaabaaeadebddeccdaabdececdaeceecabbbeeebceabbbbdebadbcccbcbdbbceeddbbddcbbceeeabbeedbddbdacedddcdabeecbddceabbccbcbededaaaacbeeaecaeccceddebeebeeacdeabbaaedcbedcebcbadaedbaddcaebadadccedeeabdeaeeaeaebaccabbeaebaedccaeadadbeaebbeceddeaecccaaadcabceadbedecddceaaedbeebeacaaebeeadceccddeebcecedaebaedacaedccbaebbedeeacecaceaaddaceaabdaeeeddacecabadabbdebccdccedcdaceeabcdeaeaedbbdeedbdcabecdcaabcaebeeabbbdeedaaecedaabbbaaecadbbbcebaeceaadccdbcaeaddccabcedaabecdeacebabbcdbbbacdbaaeebddeaaedcbccecbdaacaedccbaeaddaddaccccaceecadcadecbcecccabeccabaaceeccbeccbbdddcadbeeaeddcbbbddccacbbccbcdabbbdbbeddaaecddaecaacdcaaadaeccdbdbecededcdcaeadbdbedeeddeccbdbceddabececdaecbacabcedccceebbadeeabddabeceabaeecdaabcedacedbabcbeddddddebaaddecdacbebeadbbebbabeebcecacaebedebedeaeaddbbdbdcbcbcbadcccbddbebcacdebcedbbbacccdbaceacedabdacecdeccaaceaddbbdbeaeadcbadbeccbdccceddbcdbeccabcaaebbdaeccecdbbacbbdccbbededbdeeaeabeedbecadddcbdbcdceedecbaedbbcbabcadbbddabadcdbaeebcaaeeacbbbebbcaecedaebaecdeedcecebeebdabcbecdaecccecbbbbcbacebbaeaadabaadaebabdedcddcbcdddecdaaaaddcdedeceebbaddceeeadbbddaecaadabcedeabbcdddacbccdceeacddebaaacaccdcecbbcabeecdcbaabaececdbdebbcddeeadccddbecebbeaebbcbdddedbecccecacacabbaeababceddcdcaebebaadedddccecbebbbabbbeecddbbabbeeeeceadacadcaadcaedabdcdcacedaddececabbaeaadeebcccbeeeecbcaddacaceceedddabcccddbacbeeecbceeaeddcedaceebacddbcadbbeedaaecbbbecaeadbeaaaddeaeabdceddbbeaceaddaabcbabaecdcbcecdecdaeeeaccacddaaccdbbdeeeceedccbdeeecceaedecbeeaececaecaacbbbdcbcededbbbedbacdddcedbcaaebeaaebaeddeeeddabaddbcbcaeceedebcaacabeecedbacacedddbddcedcddbadadbdaccbbeebdbbaadadbcdeeaaebbacdbdedddcacaebbebbeeecaeacecbaaeccecbcebcdaadeeadcbddcebaeebabeddcddccacbacbceacaccbccbbcdaaebdcbacaebdaabebcaabaaebeddeaeacbcedbccbdebdccadaddacbebceaaabaebbddbcdadbcdcbdeaeecdadcbeabdadecedcdcdcdbeacddeacaaccebacaeddbbcbbdcaedadddebeddbcaeebbcdecbdaaaabcebdedacceadcccbaadedcceeccceabdbcbecccdbcbebcabbbcaebacdbedaaabcddbccadbeddccbeeceaeceacdecadedcabaeecedcbbbcaecdebbacdbdadaedaeacadbebecaaaaebadeedbdcebcecebadebeebddeecbacbadabdcceabebdbaaabaacacbebdddebcaebbbeecbdccbdcabdbddbbbadaceeaeecddcaabadeedeeebbdbbeaecbedbadcbadcecacacdaecbabadcceaadbdcbacbccdeabaabcdbdaaacdaedccbebdcbadccaddbccededeadaddaccaebabcbbdcaedaedccdacbaacecadcdbbaedbcddebadbdaedceebebacdceebeebaadaebeaeabdcbadbbaddbdabaececbaebbcdccedccbadaebdbeecaeedeeceeacdaaccecabeeaedacccccbaacaddacbbcbabbadcccaaabadcabbbadaeeaadacccacedaeecebccabcddeeadacdbaccebdabbaabadbecadadbbadeeebcbddaadececbcebbddebcebbbebccbdbedbdcebacedaeddeddaebcdbdbcbebabdbcbcbbeebaaeeeebcaceacdcdccaedabacddccbbbdabccadbcaaeeeabcbdeccbcbbddbbdaedcddabaccdacebacdccbbecaaeccadabddeaccbeeeecebdeecbceeddadadcacdecacacbddbdacbcdbadbdcddeedcceceecbaeecbcadacbbbabebceaadacceedbdcbcaedbbbaabadbceacccbbbdcbcebecbbabbdababcdbebeedebeabaabeaeaccdcdcecbdebeedbdbaaadbacdadcceeecdbababccbcbdeababbbbbeedbaaaaecccdacdeebdcaadbdcdbcccaabdbbaceceecdddecaeaddccceabadabbedbacdeddeebdceecedbabdcadeaabacaacaacacaeeccdbeebaddddeeececbababdebbadccdbaaedacadaccccceaebecedddebdcdddddeaebecabadecedddaedececddcdcabdcccedceaaececdddbdeddadabdceeaeaacceaedeeccaccedaeacccddabccdacadebcebdbbbbcedeacccdbdcbdcddebbceacbbbcedecabbecbcdcbddcebdebbeeedecbaeacddbcacbcebbbbceabdcceeaeaadeceddcabccbceeaaabebeaedaabecccaeaceacbeddddaaaceaaceceeabebcabededeeaeddedabeaeeaddaadccaeceabaeeadacaceedcbbcecededdecdbaadbecbaeccedaebacbebeecbadcadeadeebcbcbadbecdaebdbccaeaacdcdeadbdbaceacabcbcccbdbdbedeacbbdaebbbcccbeacddadcaeabcaecccbbecadcdddbcdbcbbcbadabaeccedbbcbdbecabcddeacbbeacdcdadecdccdecbdeebadceadbbdabbcedbceabadaaacdddeccbcbddeeceeebbedbcbabdbccdebaaacbbeccccebdbddbacbabbbacacdecbbbcdaacbdcddbabccdeaeeaedeebedbeacddcceecaaadeacdeeeaeaededeadddeddbbacaddbbdbdceceaedceedbaeeadbdbdbeedbadbdacbdecebecaaeebdbadecabbcdeeaccababdcbdaaebdcbbbeabdcbabdecbcbdbcceadabdeabdbbabadcebabeccbbdbabcaeebdaedeebcbacaddeabdbdcbdcbcaecacabbbeaebecbccdacdcdcceeccaeceaedacadecaeaeebbeaebdcbbdcecabbbacebcadbeedeccbaaeebdbeeadceadddeaceadddbbccadccbdbacbddccaceecadbeeddeeecaebbdbeecababcbccccbaedacadcedbbeedabbeaacdeccedeeedaadaddddcebbeeaeaeaecabdbbeaedaaacbecabaaadcdabadddbeaaedbdaaebacbbaaaeaebaedbccbcabaeabcecbeacabecaddeeeaceadcebddccbdcaadcaaacacdeacecbabdaaebdddcdedebacaeadbeecaaebaaacdcebccceddddeceaacaebddaebaeeebddbbabcccadbedcabcdbececacececbcbcebbccbcedbdcecadcbbeebccddaebeeeaddabbcbbbbaaccedcaccbadadcaadbebebaadeaceacbbcacacddcccaababceacdadcaceabcecadeddeacdaacebaabebaebeaceaabddeeccbabbdcacbdacdbdeeacaadddcacbababeeccbbaccccdacdedccdcabbddecacebedaccbbeeabedeadbcadeeaadabceccbeeedbebbbabdbacdadbeabaddceebddebdbabdbdadedcacbbbdbcbbdaacabcadbeddcacacdbcdcbbbbaedbdbcadbbaaedbddbeecabcebbebaedcdcaabdeeccdeeccaeeacabeaaacbdaeabeecaaedabbceebbbdaeeabecdadebcbcddbaaaedceeaeecbeddaaadacdccaacdbbdabaaebccdcbeaedcbeabebaaadadddaadeeededdbebbecaabbdcedebdddaadacbbbcebbccadcbaddccedcedbdebbdddccdcbbbaceaaedbecccceacbeddcebbdeacbeeecbcadcccdabebdbeecbcdaccaacdbdbdabadcabccedcbabeeecceccddcedaaddceaeedcdbebaadcdeaebabaaaedceebccbceaebeeeecbaecbacdcbedabeccaeaeaaddddaaedbebbbbbbabcadcccaabcacacecceeaecddbdabddadccddeaacdbcdceccbebddcabbcbadeccaaddeaebebedacccdceceebaaeceeeddedbaedbbcbaddeddadcbeadbeebdbdebddcacdccccbcceddaabebdcbcabcabaadadabdabadbebebcdcbaedbdeaeeadacacebbeccdeccdadeaacaeccbbbacdecdaebaceadbddcaedabceaebcaaeadaccdabedcedbabbcbbebbeecbaecdcdbadadcebddbdcbeeaccdbcdeeaabdebeaaeedbabcbdbeaaaeededddaedccedeaeecdddabcdededacaabdcccddccacddbdeceadeecbcdcdbadbcdeaeceeadedccceecdabcccccbecedbebcaaccceacbedebeaeaaecdddadeacebbaadcaadbadcbddeddbeedccdeceaebeedbdadbebdbdaceabeeaecebeaaeedabcbbadebbdeeebeaddadaeaacdeacddadcbdaabbddcdedadbebaabccdddcdeeaeecbebdaceadeebceebceddabcadcbcabbaccbcdcadcbeddddcdaddebebcbcdaaddceebcdeeebbccebecdaeeabdadcaadaeeddeeabeaecbccadbbedddbddadeeabdaebbceceabcdebeaeeebebacbdeaeecddddbaecaebeabbcdcdeecdcaeeaeccddbcbedaecebcdddecdbdccbdebeebcebeadaecbbdadbdebcebdadedcedabacdbdbcecebbaedeaceacdacaeaeceaddaceeedeacecaedcecdddaceeadbbdeaccbdbcddeddeebadebdbbedcdebdbcaeaedecdbcecbeceadbdebdadceeadaadcbbcabbeddeccdedcacaebdadeaddccccaedcbcdddbcbededdebcdaebcccaacedbbccdbdccacbdbbedcbcdbedbdbaccaedecdbceadacbdbbcbcdbbbecbcaaceabeccabaabbaddedacbcbbbabcadaabebcbcaeabccdbaaebaedeadcebedaaaabdbcbbdadbbdeadeecbdabcbeceedeeabdcabbaeaeabcebdeddbddaceacbaeabacdacbccbbaeacacbcaeebabadbebdadcacacbbcbabecabaeebbbbbadaabcbcbdaeabedccdebdadcccdabbeebdaeeadbbccddeeababbbbaebeeaaaabdeeeececcbebbacadddbbddbbcadcdaebdcdcacaabdaabcaeedebbbaebcccebccdbbaeeadaaebeeccdbebecebeedecdeaebbcadaccbaddaaabcccaecbdabbbcabbedddcdadebccbbadeabdbdcededbeedaebbdaccedaeaacaacccbdbbdcdbcdcaedbbaabbbecdaddbabababecbbaadecaebbcededbecdcaedbbcceccedcededadbaccdbabaebbacdacebaacbceeaaabcbddcecdaaaedcbdaadcdbcbbacecdbcabcadeaceedabadbbddbaacacceeabaabacbeddebbccbecabeadcecbdbddeaebeabedceababddecbceeeddbbdbbbbeeededaebeebeabbdadeedcaaebdaccecccdaccbcdeaccaabeeaaeeabdccccebacaacdbabdecaecbdecdecbcdccbeaccadaecaeadaaacdeeebbbebbcbbeceacebbbbbdddababcdddddeecebebddedececeaaebcdccbedeadebceeeadcdabebcaaeedeccdabdcbdbdeabaeccbeedcceaccdceabdadecceadcabaaeadceadbbdcaceececdadbdbaababdddedbbdcdabeececaebdeedabdaabcabcdccaebeebacacaedaeabcaaaccaeebbeceabaaaeacaddcceaddbddbcbbbcaedcdceacdebbbceaacacdbeecbcbbdcbaeedeeabcdcbabcccedeadccbbceabdbbeedddacbddcdcbaebebddcbaaebecdabbeaaaddbbbcbeeaddececbeebdaedcdacdcabdeedebaeedbedcecbbbdecddadebcdbaaebecadaeadceadeeaedbcddbedebaaebeeadabeeeadedaadcedcbbbacbadecdeebbedbbdaeaedbaaabbdbbeddaaedcdbdadeebcaeacbbaaeaeaadedcaadddccaaaddcbcbadeeeabbaeeacceaabadecbacbceeadeccaedbaaeeecddddbdabcceadddbaebabbbdbaddcecdaeaeecccbadbdaddceccbcbeaaecacdbabaeccebeebddaceabbcbcaaddbcccdacddcececbbbceccacbbdcaecbebaeaeebceadcacddbaeadadddddbeeccacabecaebaacbaaabbabbaccadcdaaeececdabbcccbaaecaeebddbcbdaccbbbeacaadbddebeddcbbdecaeddbcdbcbdeabdadbcaacebadbaeaedaedecdaccedcedabeabaedbcdeaebabddccabcbadbbdecbcecaaedadacdbcdebeabcdacdbebddcbccadecdbbbebcbeccbadbeeedbbdbdabbbbbbdecbcddadbcebedbdebbadcddebdabddbccedcebbcaeeacacdedccdcebdddaccbbbccabbbeebbdbebdbecedaaabdacddbdedcbabedeabaceccadeedaacddcbbccbcbdcdbabbcdbeeebaabeddcdaebadcecddaadaabecebdbdbbcacaedabadbcecbadcddcebceaebdddeadcbbedcdbedcacbeeadcddeecdbeebbcedbbecceaeeaebacbeeaddbcbbccbeabeabebeeccebcdaacedcabdacdcaabacedcbadcaaabaaaabaeddacacaaeaaabedccebdccacdedbcdadecddabdeadebcdedeabddaebbaaadacadbddeccdbebecacdadbbaadbaedccbeacbaabcbdccddabdbbbbebeacaebecbedebaeadabccdbbcecaeaebcaeeccaceecaaeabdbdbeeadeadcdbddcdaedbccbadaaccccabbcccdedbeeadcabedccddaadedcbcdddedaecbbcbbacbbeabdbebabdaacecbaedbaeacecbcedcbcabdededabeddbdcecbbcaebabdecacdececabcaecdebdaddadbbbaadbecaacbcbebbceccddeeecceecdbeecbadbbadedbbedcdbeceecceddebdabbbcbdceabbadacccbcddedbacadadcdccbbbccbaecbedecedabbbcacdcddcbeccadabebbaccadceadaececcdebcbbadebcbadacdedbdedededbeacaeeecacabbcaeadeacaceaeddaecdecddceccdcecaaecdccaccbbbcbbccabeeabedaebdabaabaadcbcdebabeccdedbbbcadcbcbdaebabdeebbcabacedddbcbdbdbaecaacdadebabaeadbececebeebcdddabbedaeebbecacbeeabddbdcecbeabdcabbdcbebacdabdbbeddecdbbbabacbbbeeccdadcaabbcddebeacaadbecabcaebcedaededeabbccdbadebadabcbcccadeeaacddbedbcbecbbebbeacaaccebecdaabbabcaddceebacaebceebecaaadeedaedaedccdebccbaeaeebacbabecaeaaecbdabaadcbbdabeeebdaabdbbbcaeedceaecbeedededcecebcdaadddeacecbececdecaeeeacebbbcbbabdbbdaecaaacbbdecdbabbaceaabcebcebeddacedecdedabbaadddbaebdcacbcdcdecdeaaeddeaaabbbdcccdccbcbabdcdeaaceecbaedaeeceddbebecdcbbdeeedeebdacbccddbdaecaedbbedaccbecdeaebbdcaceeaccabbadbbebeccceebbdaeccabacaeccbdbcbeebdeadbbeaadadabeabbcdcebaabbbdcdececccbcceaacbcbaeebdeaebcebaeaddabcdddaaddbcecaeaaedaceedaebadbddbadcbbbedecccbabdacbbacecaeebabdebbcdcdedcedadaacbbeeaddaeebcaccdcbdbccebdcaecbeddcbecceabcbdaddacdcddcabcbbabbddcbdddebcbeddbbabbedacceaedbabadcdaaabdcededceddedbccdcddeeeeadcaaccdeddeababcedaaedcdcaccbdbdabcaccceaabddccebadeababeaaccccaaabbbcdacabedbcbeadceecebccbacbdecdbdebbabeeddecdacdacbdaaeccdbeccbdbacbeabcaeedeceeddcedbeebeedacecddecabdabdbdabcadbdacdddcecccbcbcaecacdccecdecabbdadebdaabcacaedecbadbeebecebeacaddaabdeceeeddbdaddbaaebcaaadcaecedbcddcdbccbcddabebdcececdaeebcdccdbacbbaaecdadabdaacdcdbeadcbcecbbebbdbbadbdcebacaedebaeebebbddbccacecddcacebdceeacaeceebeeadcabacacbcbadcdeddecdeecbdacdccacdcceabcbdabeacaacaacbaecdcbadcbbeadebaabacdaecdbeacdacdaaeeedccadaadacdbaeabbedaeadbbbdbeeaeacccebececdbeeebbaeadcceedecebecabadaaeacadbdedbddddcabceccdbdaadceddebdbabeaeadbabbdaceabdbbeaecaecdccecaaceeadeebdeaebdaeaaaadcecdadcaabcdcdaaecbdaebabaeecbbcebeccdaedddcbcdedabeebccacedaddaacecdccabbacbabddccccdbaecaceecaabeeaecccaabbdcaaddcecbeceaaedbdccbecdabbbdabdababaaaacdadbdbebadcebebdbcbbcedecbacecedceaabceaaeedaeabecddaaccdaeaccddeddddebecdedbbcacbbeeababbdaceceaaeadddaddacdecdadbcedcebceeaacbceeeebdbdbcbdebcddabcdabedeebbbddbcadbabdedcdccbecbdceececbcddcbaeeddcceaacaebaddaedebbabcadbbceaeadcaaedaebbbcdedaaebbdbdadedbbbbdabcecdabbebaecbbddebeaecceaabebedecbddcceaecedbadaceccaadcdcbbabacaebecbaccbdadacdedaaacddcaaeeeeedabcbaaecceceeaabbcdedecedbcabbaadcadeabcccaddcecbbaebebceebedaebeddeeeaedabaadcdceddaaadebaabdadaeabbeadbbbaeeadaaadedeeaebbbeccbaeaddaacdbdacaababadccebbbbddcbceabbccccabbccaeaedcccbaeeabddaceabbbecbceaacabaaadaebdaeabcbceeebacdbeccdbaddbbcacbbeadbbddbdaecacbadbacdacacaaacbccebeadeadccbcccceebeeddebaaeabcbececddbccdaddbbbbbadaeaeebeeeccdaaacceaeaaaaabacbdccdccbbebcbdcbacadacebbacdebaedcdeeaddccedcdeabebddccedbabeeaacedcceccaacdbeabecccadcccbccacbacebcdedcedddbeddacddcbbdeaaceaeebbceadbceebcadbbebbbaecedeecaaebddaecebdeebaeeebcdcbebacedaaadaadbbdaedeaedbbbadbecdddbeaaabcccbcccecedaccaedbecbbcdcddebdcceccedacbabaaddbbdeaddccaebabadbaeeebaeadbeebaeeaaabbaaebeceaabeeaebcdbbaeadbbdbacdadbedecdeebeeeaebcbaaacdccacacecabbdbceddddeabeaaaaadaaadcebbaacedcabcdbbcacaccadbbdaebcdedadddccaaabaecebbbccabdabccabebeadebaaebdeaabbcebcbcdaadbaedcbadbcdbbbeccccaaddedbcddebaddbcaabbecccaecbaacaedabcaccaceacecacabdbacdeebaecdaeeebdddeadddeceabbbbacdaaaaeaabdaedbdcdcaadeecedeeddacedebcdebedecbecceecabcdeecbcbbadabedbadbeebbaadcebbbceacccdeabdaaeabdabebbdcbcdeaecdcbcbacdbceaccdeaeaedabdeaabcdcabbbbbbdaaccbabddcbcddbcaacedcdadaaadcbbbbddddeeeeaecddbcbbbdeaaecbcbacdeccecabdcaeaedcdcadbcacbdbeadaeebabacbceabacdcbecbacbdedabacaeddeaadaeaaebcccbdadcdccaedbaddcbaacadbadeeeebbdeccdeeeeabadedeebbcdbdbbecdbeeadeaeeedebcabacebedbceeacbcccbaadacbeeedaaeebbedeedddaebaaaeeaddcddaccbdadbdbbbadebaaecedebddeaedbdebdeddcabbcdcdceabdcdbbabdeddeedcbdbcbbbdcdbddadadeaebbdddaaeddceadcbaececdadcddcbcbebeccdbbbebabaddabeebabeceeededdabaaabacdcdbdaabceccdbbdaceaeedbaccddcaeaccbededecaccbcaebdabcdadbcbbdedcacbeccdacdaabccbabedbeaeaeaabeadeceddbbcdddbeaedcebcccececadaddeeeebbeebcbaeadeadbcddaaaccebdedbddbeeabdaccaaacadebbdacaaebbadeeabbcbbbcbcacaaaecacddbbcbdcdcebbedadcabcccdebabbecabcaebbdcaedbdaddeaecaeebbadceccadddacdeeabdeaeecceccbedbdabdceedcccadbaccaeadecebbecadeeebdaeaebedaeaeeebdddebbaebadacbcbaebebbcdccaeedacaccdeabecabaeccdebaeaeadbeebeacbcbdaaedeebcaddbbdccbdaebdeadabcdbcbaeacadaeaaddececcaabdcceaeeddebdcecedacedaaedacddbbcabdbeaabbddedaebeeeccceeebaecddbcecaecccecdaaddeeaedbdbacbabedbabeeccedcdbbacbabbacbdbaeeddadaabdbaecbdeaaddeacebababcacaecbebdabedeceabdbacdebeadcbeabedacdbedaceadcbeabddecdcccbbebaeebcbaadcdbbddbdccbdcceadaeaceaccecbcebabadcabbeaddcacecbcccbebaeaddbbeebaaaeebbeebdadcdaeebeacedcbeaaadedbcdbbdeeeedaebccacacedaacbebbcccbdbdbbadedbdbadddacabadeabeebeeadedeeadacccdcdeebbebbdeabbbecaadaebddedddeaceebbccdabeeeeaaeacdbecdbbabbcdaacddaeaaaaddcddbcdcdcdaebdadbdaedcdedaaddbadecccbddeeedddbbcadcaeedcbdabbbdbcbbbabaeeceacbdbeeadbeeabdbadbeabbbdaecbeeddbccbceaccbbdabbaedbecabbdadcabcebbbaeebddbcebceaadcadeaedabadbdcbeccedecbceddddaeaebabadadcdbddeecacdbebbdccdbeeaabedccceabecdeedcbedddceedbcccdddcbdebddddbdabaacdabaeedbabaddececeadadaeedddabdbcdcbdeddebbbaaeccdccbaccacbeddeebedeabccdacbaabadebcbdaeceaccaadedaacdbebecccbedcdddecddcaacbbceedadcbdbddaaebebdecbddeeeceaacccabcebdaecbbaeedbdbddddcbecbdddeebecdaacbbdcaaedbbaddedcdcabddbdcbaacaadaabddbceeecbdebaadbbccdecaedbedcbebcdacdcaceaedcebddacbcbaecebcddcbdecaabeaebeddaeddecdbcdeabbdaeedabdccbcadededccccbebcdeacdbdabdcdcbbdbdaabcdedbbdeeebcadeebecbbeedbdebcababdeeaeeecaccacaaeceeabaacbccadceeecccaceaacbcaccdebeaeccdebbdeebcadadcadbceecabdcebebabeaebbaadadadcbcbacdecbebebbaabddcdaeaedcbecaaecabcadcdeadddbadbaccdbbcdbebceceeaabcdbecbcdbadeedaccaecbaeecabeacabbacebceeebebaddeeccdceaacbaacddecadbebadbddbcbaeaeaaccdebadcacddedadeadbbcabccdcceeecbacbccbadaeaaacecebbadadbadeeaabaebcedbeeceaeccceebbdbecbcebceeaaeaebcdcabcaeddacaaacbdedbbaaeebbaabdbdacabecbddaedaddeeeedccecdecdbcccaeecddebbbadbeebcaabccdaaeacabbaddcaceabebedebbddaaaacddedcedcedcbbabaabbaeaeaddbcccdeddacadacacabeebcbabbbbedecccecebbebccadeddacbbacedaebdbcccdcbaccbceeabaedeeaccbaebacdbddaebeecdcaeccddaadedddcadedcbdcecbbaaabcbbeeebaabdeeebbedcdcabaeddcccedaedbddbdbcdadebecacbdaeabebeddabadcbbbedbebbededeccecabaddddedebdebeebccbabcedcddebcccbcbdaaebdcecbeedceededecaedacebaeedaecabeaedaeeadebdccceedbaddeebebddcbcedaacdcaebaccdeabeabcabbdcaecedcbadbcacbbabbdabaedaeaeecdacbeddbcdbadeacbcaacecaabcabcacdbaecbbaebaaabdcedcaabdcebbdedcabdbaaeecbeebddeceddacebadececacccdebbcdecdceadcebacbaabdddeccbedeeaedaeabadbcacaedaacccacaabebcaebeccdabbceddeccdbbeeeccddbaabbaeecddabcbdbeadacaccbbbabeceedaabcbbbaaaedadebaaceabcdcddabeaecaebbaceceeabbebdeaecbccdbcadceebeacaeceaebaecacccdebcabecbecdbaacbeccbcacebdaaceedddedbbbdcdbccddaececadbbbcbddbdbadeccdebacbebababbdedcaceeaeebcdaabdbacccdeabadcdebbaaeaadaebdcaeedacedcaebcaeabdcdababeacbaddaeccceedcaedddbcecacadbacadbcdaeeceeeabbbadcaaaadaebdccabbbadedadbdcdcbccdabeedecadabdedaaacaacdaecbcdbbcaabdcdbebcaccbeecbebcebaadccddebdbdceedccbcbdcecebeabceecbcaddaccaceaccebbdeecddbecdbbadeaedaecceacceeddcacccdeeeecdbbbccaaccecaecaabcccdabdbbaabebdcecbbabaeadddeebacabebceabbdeabbdcabdaebdcecceabaabcbbbadbeeabacebaaeddedaecaccddebebccdbdcabdecbdaeababbcdeccadddbecbebbedecaaecbdbccadbddddaaacecebbbbcbedadbbabcbdccccedcdbdbaaeecacbbecaaccadcdaebdcbededceeedddedabadeadadbcbdceaebcddddebcccdeebbacecaaccadedcbadabdbedcbbebdccbbecacabbdbacdbdecdebcacacdabddbdbbecbcecddcceabebebeeabcdceecedbeddacbcaedaeedabcbdeedabaeecabacddeccdebacdbdeabcebcabeddbdcaebacdcbcbbbbeaeceebadecebaddcdeddccebabdccaadaeadbdadeddcaecacdeaccbdabdcbdbdcdadceeedaecbeeebaaedeaddbdbeabceecbccbebeaceeeaceabddbdbbedabbbdaecaddabdcbddadeccbaeeaecdeaeedaecaacbbaaecabccbcbadeabdcabedbcecbbdedaebedcdbeebedebdcedbbdceeedbbcaabadabcdcabaebacdcbcdcccaceeceddadeaadebceebccbacedbdaceadeacadeecceeaebadceeacaacdedaecaeccdcaaabceeaabdecaabceeaacaadaaddccdbdbadcebeddbbadadbbaaadeadbbbdddebebbbaabcdebbcaeddbbacabdddedeababbabdadeecdabbeecdaeaedcdddcdedebceacaccadcccabadbedaecbeaeebeceacbbbabbcdeadeebaabeeccadddbccaeeddddbbeecaecbdccbeadacdbaedadaeddcaeaedaeaeacdadcedcdabddacededcbeebaabeadaabbeeddeeababbaacabdbeadeadeedceadcbecddacaeaceeebcecadaebdccaeacdedbbecacabddeeeadecddbacddbebeedacdeddacbbbcebbaecaecadccccdebccdcdcbacbcccbdabdadaababdacebddcceddbdecdacbadaaaeaeddeeabcebbccbdbbebedabbdbdcaedebaaecddbacbaaaccdadeddebebdbabeceeaadadaabceecdceadebecacacbaebaebebceccdeebcabedaabcabccabedbbebabaababedeebaabcdaacdcccebcaecceedeebeabeadacbbcdcbbcdbddbcdadbcaceddedabeebbeedaabbccacdacedabbdeacbeebceadcaeacdbceaceaaaeebcbbebdeddbbbeddcbcabaacaadebcdceadcadaececbbbeecddcbbdbcdecaaacedbcbdbeabbbbdeceaebdcddbbebdbebbbcabccaecacbbcaeadcdbcdaadccaceddedaabaabcacacaeddcceadbabdbcbdaeeacabacdcdcbccaedeceacaaadabeabbceeedaabdcdbddebddadbadbbddedecabbbbdabecedbbcceacaacbebdeddbedbeabdbbadbeacbeabceaddadeeececeaaacecaaacbdcdcbcddcecadbbeceadebadececacaeaeccbdbddeadabcebaeeaeeabeccebdaeadaeedddaeaaedabcdbcaaeacabdcaaccbadbeabdbcbdcbeddabdacebcecccddcacbbccedbecbdcdbdeeaaaeeecacbacabbcccccaecacdececaeceacacecbdcbceaedcbdabeecbabbeaadbaaaeceabbaacbbbbddaeeadabaadcadcbeeabececbededccbddcbcdeacaacbabaaaebdcbcecdcbdbbdcbaeeebdaaecccbbbabdaddbdceaaacabdaccaeaccecdadcebdbceddbcbbcebdbbaccedbbeeceaeadbbbaabdaeaeccdcebceebdddaaaaeaeabdbebeddbadbbbddadadadcbccebecccdeeeaaeddaacadbbbbccecbbcdcebeeeaecbedbeecabcdceaeeadaeccecbbcddbacbdbcbbdceeedccbdeadbeeaacaeccaebdabbecabaeecdbdbcacdbcbadcbeeedbcebaacdaccbbcecdbdebabacddddaeadcdddcbedabbcbedcadbabeedeecbadbacbddaccadebcbaadbcbdabedccbbecbbbccabdaeacdaddcdceebedccdaddcdeccacecacbcedaccdbdbcbeeedaabbeddcaaacaceabcecacebcdacecaceabbccccdcbacaeaeebbbbecbecdbcabecccdebacbadcbaeecdcaaabaaecaacdaaccdbaaacdadecadaeecccdacebdddecbaacedbedbcbbbeabdabcdcedadcaebbebaeeebddbebcddabbbdedbeadeaebaccabecdbcbeaaabadbeccccaddbacddacbaeaecccadedaddedbebcecebcdadaccdcbedacbcbdcddceedaebedecdedeaecbeadbccedcbbaedccbeaeebaababeccdbdbdbcddcaaebcbcbaabbdaaabcccbbaeeaabbccddeebadebbdcebdaadbabdcacdeeeacedeaccabcbbeaabcdaecbdacecdabdbabaaadcadcdacaeeccabcaebcdcceaeccbaddecbceccddbbdbbbbadbdadeeaedcdbeddbbbddcebeaadbedebdddbcbddaacaceccbacbacebaebbbcbacddbaacedeeedbcadaaebdababbddabbcbddaccdcddbbdeabaacaeaaddacedaaceeedcedcecceaadbdebdcbeeaabaeca".to_string();
    let res = "ddbcddbabee".to_string();
    assert_eq!(Solution::longest_dup_substring(s), res);
}

Having problems with this solution? Click here to submit an issue on github.