Palindrome tree
کمپیوٹر سائنس میں پیلینڈروم ٹری، جسے ایرٹری بھی کہا جاتا ہے، سرچ ٹری کی ایک قسم ہے، جو سٹرنگ میں موجود تمام پیلینڈروم تک تیزی سے رسائی کی اجازت دیتی ہے۔ ان کا استعمال سب سے طویل پیلینڈرومک سبسٹرنگ، کے-فیکٹرائزیشن کا مسئلہ (کیا کسی دی گئی سٹرنگ کو بالکل کے پیلینڈروم میں تقسیم کیا جا سکتا ہے)، سٹرنگ کی پیلینڈرومک لمبائی (سٹرنگ کی تعمیر کے لیے درکار پیلینڈروم کی کم از کم تعداد کیا ہے)، اور تمام الگ الگ ذیلی پیلینڈروم کو تلاش کرنے اور گننے کے لیے کیا جا سکتا ہے۔ پیلینڈروم کے درخت یہ کام آن لائن طریقے سے کرتے ہیں، یعنی اسے شروع میں پوری تار کی ضرورت نہیں ہوتی ہے اور اسے کردار کے لحاظ سے کردار میں شامل کیا جا سکتا ہے۔ تفصیل زیادہ تر درختوں کی طرح، پیلینڈروم کا درخت عمودی اور سمت والے کناروں پر مشتمل ہوتا ہے۔ درخت میں ہر سرے ایک پیلینڈروم کی نمائندگی کرتا ہے (مثال کے طور پر۔ 'ٹیکوکیٹ') لیکن صرف پیلینڈروم کی لمبائی کو ذخیرہ کرتا ہے، اور ہر کنارے یا تو ایک کردار یا لاحقہ کی نمائندگی کرتا ہے۔ کردار کے کنارے اس بات کی نمائندگی کرتے ہیں کہ جب کردار کو پیلینڈروم کے دونوں سروں پر جوڑا جاتا ہے جس کی نمائندگی ماخذ ورٹیکس کرتا ہے، تو منزل کے ورٹیکس میں پیلینڈروم بن جاتا ہے (جیسے۔ 'ٹی' کا لیبل لگا ہوا ایک کنارہ ماخذ ورٹیکس 'اکوکا' کو منزل کے ورٹیکس 'ٹیکوکیٹ' سے جوڑ دے گا)۔ لاحقہ کنارے ہر پیلینڈروم کو اس کے پاس موجود سب سے بڑے پیلینڈروم لاحقہ سے جوڑتا ہے (پچھلی مثال میں 'ٹیکوکیٹ' کا لاحقہ کنارے 'ٹی' ہوگا، اور 'اٹاکوکاٹا' کا لاحقہ لنک 'اٹا' ہوگا)۔ جہاں پیلینڈروم کے درخت عام درختوں سے مختلف ہوتے ہیں، وہ یہ ہے کہ ان کی دو جڑیں ہوتی ہیں (کیونکہ وہ حقیقت میں دو الگ الگ درخت ہیں)۔ دونوں جڑیں لمبائی −1، اور 0 کے پیلینڈروم کی نمائندگی کرتی ہیں۔ یعنی اگر حرف 'a' کو دونوں جڑوں سے جوڑا جائے تو درخت بالترتیب 'a' اور 'aa' پیدا کرے گا۔ چونکہ ہر کنارے میں حروف کی ایک یکساں تعداد شامل ہوتی ہے (یا ہٹا دی جاتی ہے)، اس لیے دونوں درخت ہمیشہ صرف لاحقہ کناروں سے جڑے رہتے ہیں۔ آپریشنز ایڈ چونکہ پیلینڈروم کا درخت ایک آن لائن تعمیر کی پیروی کرتا ہے، اس لیے یہ درخت میں شامل کیے گئے آخری پیلینڈروم کی طرف اشارہ کرتا ہے۔ پیلینڈروم ٹری میں اگلے کردار کو شامل کرنے کے لیے، ایڈ (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) شامل کرنے کے لیے مساوی تعداد میں کالوں کے ذریعے ایک سے زیادہ بار درخت کو اوپر لے جانے کی لاگت 'ادا' کی جاتی ہے۔ جگہ ایک پیلینڈروم درخت جگہ لیتا ہے: زیادہ تر عمودی حصوں میں ذیلی پیلینڈروم اور دو جڑوں، کناروں کو ذخیرہ کرنے کے لیے، عمودی حصوں اور لاحقہ کناروں کو جوڑتا ہے۔ اگر ہر پیلینڈروم کے لیے موجود صرف اضافی کناروں کو ذخیرہ کرنے کے بجائے لمبائی کے کناروں کی ایک صف ذخیرہ کی جاتی ہے، تو صحیح کنارے کو تلاش کرنا مستقل وقت میں تعمیر کے وقت کو کم کرتے ہوئے جگہ کو بڑھاتے ہوئے کیا جا سکتا ہے، جہاں پیلینڈروم کی تعداد ہے۔ حوالہ جات کے درخت (ڈیٹا ڈھانچے)