Palindrome tree
કોમ્પ્યુટર વિજ્ઞાનમાં પેલિનડ્રોમ વૃક્ષ, જેને એર્ટ્રી પણ કહેવાય છે, તે એક પ્રકારનું શોધ વૃક્ષ છે, જે શબ્દમાળામાં સમાવિષ્ટ તમામ પેલિનડ્રોમને ઝડપી ઍક્સેસ માટે પરવાનગી આપે છે. તેનો ઉપયોગ સૌથી લાંબી પેલિનડ્રોમિક સબસ્ટ્રિંગ, કે-ફેક્ટરાઇઝેશન સમસ્યા (આપેલ સ્ટ્રિંગને બરાબર કે પેલિનડ્રોમ્સમાં વિભાજિત કરી શકાય છે), સ્ટ્રિંગની પેલિનડ્રોમિક લંબાઈ (સ્ટ્રિંગ બનાવવા માટે જરૂરી પેલિનડ્રોમ્સની ઓછામાં ઓછી સંખ્યા કેટલી છે), અને તમામ અલગ-અલગ પેટા-પેલિનડ્રોમ્સ શોધવા અને ગણતરી કરવા માટે થઈ શકે છે. પેલિંડ્રોમ વૃક્ષો આ ઑનલાઇન રીતે કરે છે, એટલે કે તેને શરૂઆતમાં સમગ્ર સ્ટ્રિંગની જરૂર નથી અને અક્ષર દ્વારા અક્ષરમાં ઉમેરી શકાય છે. વર્ણન મોટાભાગના વૃક્ષોની જેમ, પેલિંડ્રોમ વૃક્ષમાં શિરોબિંદુઓ અને નિર્દેશિત ધાર હોય છે. વૃક્ષમાં દરેક શિરોબિંદુ પેલિંડ્રોમનું પ્રતિનિધિત્વ કરે છે (દા. ત. 'ટેકોકેટ') પરંતુ માત્ર પેલિંડ્રોમની લંબાઈને સંગ્રહિત કરે છે, અને દરેક ધાર ક્યાં તો અક્ષર અથવા પ્રત્યયનું પ્રતિનિધિત્વ કરે છે. અક્ષરની ધાર રજૂ કરે છે કે જ્યારે અક્ષરને પેલિનડ્રોમના બંને છેડા સાથે જોડવામાં આવે છે જે સ્રોત શિરોબિંદુ દ્વારા રજૂ થાય છે, ત્યારે ગંતવ્ય શિરોબિંદુમાં પેલિનડ્રોમ બનાવવામાં આવે છે (દા. ત. 'ટી' લેબલવાળી ધાર સ્ત્રોત શિરોબિંદુ 'એકોકા' ને ગંતવ્ય શિરોબિંદુ 'ટેકોકેટ' સાથે જોડશે). પ્રત્યય ધાર દરેક પેલિંડ્રોમને તેની પાસેના સૌથી મોટા પેલિંડ્રોમ પ્રત્યય સાથે જોડે છે (અગાઉના ઉદાહરણમાં 'ટેકોકેટ' ની પ્રત્યય ધાર 'ટી' હશે, અને 'એટાકોકાટા' ની પ્રત્યય કડી 'અતા' હશે). જ્યાં પાલિંડ્રોમ વૃક્ષો સામાન્ય વૃક્ષોથી અલગ પડે છે, તે એ છે કે તેમના બે મૂળ હોય છે (કારણ કે તે હકીકતમાં બે અલગ વૃક્ષો છે). બે મૂળ −1, અને 0 લંબાઈના પેલિનડ્રોમ્સનું પ્રતિનિધિત્વ કરે છે. એટલે કે, જો 'અ' અક્ષર બંને મૂળ સાથે જોડવામાં આવે તો વૃક્ષ અનુક્રમે 'અ' અને 'આ' ઉત્પન્ન કરશે. દરેક ધાર સરખી સંખ્યામાં અક્ષરો ઉમેરે છે (અથવા દૂર કરે છે), તેથી બે વૃક્ષો માત્ર પ્રત્યય ધાર દ્વારા જોડાયેલા હોય છે. પેલિન્ડ્રોમ વૃક્ષ ઓનલાઇન બાંધકામને અનુસરે છે, તેથી તે વૃક્ષમાં ઉમેરવામાં આવેલા છેલ્લા પેલિન્ડ્રોમ માટે નિર્દેશક જાળવે છે. પેલિનડ્રોમ વૃક્ષમાં આગળનું અક્ષર ઉમેરવા માટે, (x) ઉમેરો પહેલા તપાસો કે પેલિનડ્રોમ પહેલાનું પ્રથમ અક્ષર ઉમેરવામાં આવતા અક્ષર સાથે મેળ ખાય છે કે કેમ, જો તે ન થાય, તો જ્યાં સુધી વૃક્ષમાં પેલિનડ્રોમ ઉમેરી ન શકાય ત્યાં સુધી પ્રત્યય કડીઓ અનુસરવામાં આવે છે. એકવાર પેલિંડ્રોમ મળી ગયા પછી, જો તે વૃક્ષમાં પહેલેથી જ અસ્તિત્વમાં હોય, તો ત્યાં કોઈ કામ નથી. નહિંતર, પ્રત્યયથી નવા શિરોબિંદુ સુધીની કડી સાથે નવું શિરોબિંદુ ઉમેરવામાં આવે છે, અને નવા શિરોબિંદુ માટે પ્રત્યય કડી ઉમેરવામાં આવે છે. જો નવા પેલિંડ્રોમની લંબાઈ 1 હોય, તો પ્રત્યય કડી પેલિંડ્રોમ વૃક્ષના મૂળ તરફ નિર્દેશ કરે છે જે −1 ની લંબાઈને રજૂ કરે છે. #S-> ઇનપુટ શબ્દમાળા #x-> અક્ષરની સ્ટ્રિંગમાં ડિફ એડ (x: int)-> બૂલઃ "" પેલિંડ્રોમ વૃક્ષમાં અક્ષર ઉમેરો "". જ્યારે સાચુંઃ જો x-1-current.length = 0 અને S [x-1-current.length] = = S [x]: વિરામ પ્રવાહ = current.suffix જો current.add [S [x] કોઈ નથીઃ પરત કરો ખોટો પ્રત્યય = વર્તમાન પ્રવાહ = પાલિન્ડ્રોમ _ વર્ટેક્સ () current.length = suffix.length + 2 suffix.add [S [x] = વર્તમાન જો current.length = = 1: current.suffix = રુટ રીટર્ન સાચું હોય જ્યારે સાચુંઃ પ્રત્યય = suffix.suffix જો x-1-suffix.length = 0 અને S [x-suffix.length = = S [x]: current.suffix આ દરેક શિરોબિંદુ પર લંબાઈની શ્રેણી ઉમેરીને અને જો શબ્દમાળા ઉમેરતી વખતે તે શિરોબિંદુ સુધી પહોંચી ગયું હોય તો અનુક્રમણિકા પર ધ્વજને 1 પર સેટ કરીને પરિપૂર્ણ થાય છે. એકમાત્ર અન્ય ફેરફાર જરૂરી છે કે વર્તમાન નિર્દેશકને દરેક શબ્દમાળાના અંતે મૂળમાં રીસેટ કરવું. વૃક્ષોને આ રીતે જોડીને નીચેની સમસ્યાઓનું સમાધાન કરી શકાય છેઃ તમામ તાર માટે સામાન્ય પેલિનડ્રોમની સંખ્યા એક તારમાં અનન્ય પેલિનડ્રોમની સંખ્યા તમામ તાર માટે સૌથી લાંબો પેલિનડ્રોમ અન્ય કરતાં એક તારમાં વધુ વખત જોવા મળતા પેલિનડ્રોમની સંખ્યા જટિલતા પેલિનડ્રોમ વૃક્ષનું નિર્માણ કરવામાં સમય લાગે છે, જ્યાં તારની લંબાઈ અને મૂળાક્ષરોનું કદ છે. (x) ઉમેરવા માટેના કૉલ્સ સાથે, દરેક કૉલ ઋણમુક્ત સમય લે છે. આ ઉમેરવા માટેના દરેક કોલનું પરિણામ છે (x) વર્તમાન શિરોબિંદુ (વૃક્ષમાં છેલ્લો પેલિંડ્રોમ) ની ઊંડાઈમાં વધુમાં વધુ એક વધારો કરે છે, અને શિરોબિંદુની તમામ સંભવિત અક્ષર ધારને શોધવામાં સમય લાગે છે. (x) ઉમેરવા માટે દરેક કોલમાં વૃક્ષને ઉપર અને નીચે ખસેડવાનો ખર્ચ સોંપીને, વૃક્ષને ઉપર ખસેડતી વખતે (x) ઉમેરવા માટે સમાન સંખ્યામાં કોલ દ્વારા વૃક્ષને એકથી વધુ વાર ઉપર ખસેડવાનો ખર્ચ 'ચૂકવવામાં આવે છે'. પેલેન્ડ્રોમ વૃક્ષ જગ્યા લે છેઃ મોટા ભાગના શિરોબિંદુઓ પર પેટા-પેલેન્ડ્રોમ અને બે મૂળ, ધાર, શિરોબિંદુઓ અને પ્રત્યય ધારને જોડતા સંગ્રહિત કરવા માટે. સ્પેસ-ટાઇમ ટ્રેડઓફ જો દરેક પેલિનડ્રોમ માટે અસ્તિત્વ ધરાવતી માત્ર એડ ધારને સંગ્રહિત કરવાને બદલે લંબાઈની ધારની શ્રેણી સંગ્રહિત કરવામાં આવે, તો યોગ્ય ધાર શોધવાનું બાંધકામના સમયને ઘટાડીને સતત કરી શકાય છે, જ્યારે જગ્યા વધારીને, જ્યાં પેલિનડ્રોમની સંખ્યા છે. સંદર્ભ વૃક્ષો (માહિતી માળખાં)