Palindrome tree
கணினி அறிவியலில், ஈர்ட்ரீ என்றும் அழைக்கப்படும் பாலிண்ட்ரோம் மரம் என்பது ஒரு வகை தேடல் மரமாகும், இது ஒரு சரத்தில் உள்ள அனைத்து பாலிண்ட்ரோம்களையும் விரைவாக அணுக அனுமதிக்கிறது. நீண்ட பாலிண்ட்ரோமிக் அடி மூலக்கூறு, கே-காரணிமயமாக்கல் சிக்கல் (கொடுக்கப்பட்ட சரத்தை சரியாக கே பாலிண்ட்ரோம்களாகப் பிரிக்க முடியுமா), ஒரு சரத்தின் பாலிண்ட்ரோமிக் நீளம் (சரத்தை உருவாக்கத் தேவையான குறைந்தபட்ச பாலிண்ட்ரோம்களின் எண்ணிக்கை என்ன), மற்றும் அனைத்து தனித்துவமான துணை-பாலிண்ட்ரோம்களையும் கண்டுபிடித்து எண்ணுவதற்கு அவை பயன்படுத்தப்படலாம். பாலிண்ட்ரோம் மரங்கள் இதை ஆன்லைன் முறையில் செய்கின்றன, அதாவது இதற்கு ஆரம்பத்தில் முழு சரமும் தேவையில்லை, மேலும் எழுத்துக்கு ஏற்ப சேர்க்கலாம். பெரும்பாலான மரங்களைப் போலவே, ஒரு பாலிண்ட்ரோம் மரமும் செங்குத்துகள் மற்றும் திசைப்படுத்தப்பட்ட விளிம்புகளைக் கொண்டுள்ளது. மரத்தில் உள்ள ஒவ்வொரு முனையும் ஒரு பாலிண்ட்ரோமைக் குறிக்கிறது (எ. கா. 'டகோகாட்') ஆனால் பாலிண்ட்ரோமின் நீளத்தை மட்டுமே சேமிக்கிறது, மேலும் ஒவ்வொரு விளிம்பும் ஒரு எழுத்து அல்லது பின்னொட்டு குறிக்கிறது. எழுத்து விளிம்புகள், மூல உச்சியால் குறிக்கப்படும் பாலிண்ட்ரோமின் இரு முனைகளிலும் எழுத்து இணைக்கப்படும்போது, இலக்கு உச்சியில் உள்ள பாலிண்ட்ரோம் உருவாக்கப்படுகிறது (எ. கா. 'டி' என்று பெயரிடப்பட்ட ஒரு விளிம்பு மூல உச்சியை 'அகோகா' இலக்கு உச்சியை 'டகோகாட்' உடன் இணைக்கும்). பின்னொட்டு விளிம்பு ஒவ்வொரு பாலிண்ட்ரோமையும் அது வைத்திருக்கும் மிகப்பெரிய பாலிண்ட்ரோம் பின்னொட்டியுடன் இணைக்கிறது (முந்தைய எடுத்துக்காட்டில் 'டகோகாட்' என்பது 'டி' என்ற பின்னொட்டு விளிம்பைக் கொண்டிருக்கும், மேலும் 'அடாகோகாடா' என்பது 'அட்டா' என்ற பின்னொட்டு இணைப்பைக் கொண்டிருக்கும்). பாலிண்ட்ரோம் மரங்கள் வழக்கமான மரங்களிலிருந்து வேறுபடுகையில், அவை இரண்டு வேர்களைக் கொண்டுள்ளன (அவை உண்மையில் இரண்டு தனித்தனி மரங்கள் என்பதால்). இரண்டு வேர்களும் −1 மற்றும் 0 நீளமுள்ள பாலிண்ட்ரோம்களைக் குறிக்கின்றன. அதாவது, 'அ' என்ற எழுத்து இரண்டு வேர்களுடனும் இணைக்கப்பட்டால், மரம் முறையே 'அ' மற்றும் 'ஆ' ஐ உருவாக்கும். ஒவ்வொரு விளிம்பும் சம எண்ணிக்கையிலான எழுத்துக்களைச் சேர்ப்பதால் (அல்லது நீக்குவதால்), இரண்டு மரங்களும் எப்போதும் பின்னொட்டு விளிம்புகளால் மட்டுமே இணைக்கப்படுகின்றன. ஒரு பாலிண்ட்ரோம் மரம் ஒரு ஆன்லைன் கட்டுமானத்தைப் பின்பற்றுவதால், அது மரத்தில் சேர்க்கப்பட்ட கடைசி பாலிண்ட்ரோமுக்கு ஒரு சுட்டியை பராமரிக்கிறது. பாலிண்ட்ரோம் மரத்தில் அடுத்த எழுத்தைச் சேர்க்க, சேர் (x) முதலில் பாலிண்ட்ரோமுக்கு முந்தைய முதல் எழுத்து சேர்க்கப்படும் எழுத்துடன் பொருந்துகிறதா என்பதைச் சரிபார்க்கிறது, இல்லையென்றால், மரத்தில் ஒரு பாலிண்ட்ரோமைச் சேர்க்கும் வரை பின்னொட்டு இணைப்புகள் பின்பற்றப்படுகின்றன. ஒரு பாலிண்ட்ரோம் கண்டுபிடிக்கப்பட்டவுடன், அது ஏற்கனவே மரத்தில் இருந்திருந்தால், செய்ய எந்த வேலையும் இல்லை. இல்லையெனில், பின்னொட்டு முதல் புதிய உச்சிக்கு ஒரு இணைப்புடன் ஒரு புதிய உச்சி சேர்க்கப்படுகிறது, மேலும் புதிய உச்சிக்கு ஒரு பின்னொட்டு இணைப்பு சேர்க்கப்படுகிறது. புதிய பாலிண்ட்ரோமின் நீளம் 1 ஆக இருந்தால், பின்னொட்டு இணைப்பு-1 நீளத்தைக் குறிக்கும் பாலிண்ட்ரோம் மரத்தின் வேரை சுட்டிக்காட்டுகிறது. #எஸ்-> உள்ளீட்டு சரம் #எக்ஸ்-> சேர்க்கப்பட்ட எழுத்தின் சரத்தில் உள்ள நிலை டிஃப் ஆட் (எக்ஸ்ஃ இன்ட்)-> பூல்ஃ "பாலிண்ட்ரோம் மரத்தில் எழுத்தைச் சேர்க்கவும்". உண்மை என்றால்ஃ 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) சேர்க்க சம எண்ணிக்கையிலான அழைப்புகளால் மரத்தை ஒன்றுக்கு மேற்பட்ட முறை நகர்த்துவதற்கான செலவு 'செலுத்தப்படுகிறது' இல்லை. ஒரு பாலிண்ட்ரோம் மரம் இடத்தை எடுக்கும்ஃ பெரும்பாலான செங்குத்துகளில் துணை-பாலிண்ட்ரோம்கள் மற்றும் இரண்டு வேர்கள், விளிம்புகளை சேமிக்க, செங்குத்துகள் மற்றும் பின்னொட்டு விளிம்புகளை இணைக்கிறது. ஒவ்வொரு பாலிண்ட்ரோமுக்கும் இருக்கும் கூடுதல் விளிம்புகளை மட்டுமே சேமிப்பதற்குப் பதிலாக நீள விளிம்புகளின் வரிசை சேமிக்கப்பட்டால், சரியான விளிம்பைக் கண்டுபிடிப்பது நிலையான நேரத்தில் கட்டுமான நேரத்தைக் குறைத்து, இடத்தை அதிகரிக்கும் போது, பாலிண்ட்ரோம்களின் எண்ணிக்கை எங்கே. குறிப்புகள் மரங்கள் (தரவு கட்டமைப்புகள்)