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) যোগ করার জন্য সমান সংখ্যক কল দ্বারা একাধিকবার গাছটি উপরে সরানোর খরচ 'পরিশোধ করা হয়' ঘটেনি। একটি প্যালিন্ড্রোম গাছ স্থান নেয়ঃ বেশিরভাগ শীর্ষে সাব-প্যালিন্ড্রোম এবং দুটি শিকড়, প্রান্ত সংরক্ষণ করতে, শীর্ষ এবং প্রত্যয় প্রান্তগুলিকে সংযুক্ত করে। স্পেস-টাইম ট্রেডঅফ যদি প্রতিটি প্যালিনড্রোমের জন্য বিদ্যমান অ্যাড এজগুলি সংরক্ষণ করার পরিবর্তে দৈর্ঘ্যের প্রান্তগুলির একটি অ্যারে সংরক্ষণ করা হয়, তবে সঠিক প্রান্তটি খুঁজে বের করা স্থির সময়ে নির্মাণ সময়কে কমিয়ে স্থান বাড়ানোর সময় করা যেতে পারে, যেখানে প্যালিনড্রোমের সংখ্যা কোথায়। তথ্যসূত্র গাছ (তথ্য কাঠামো)