آرایه ال‌سی‌پی
در علوم رایانه، آرایه بلندترین پیشوند مشترک (آرایه ال‌سی‌پی) یک داده‌ساختار کمکی برای آرایه پسوندی است. در این آرایه، طولانی‌ترین پیشوند مشترک بین هر دو پسوند متوالی موجود در آرایه پسوندی ذخیره می‌شود.
آرایه ال‌سی‌پی توسط و در سال ۱۹۹۰ به همراه آرایه پسوندی و برای بهبود سرعت الگوریتم جستجوی الگو در متن ارائه شد.
فرض کنیم formula_1 آرایه پسوندی رشته formula_2 بوده و formula_3 نشان‌دهندهٔ طولانی‌ترین پیشوند مشترک رشته‌های formula_4 و formula_5 باشد. هم چنین زیررشتهٔ formula_6 از حرف formula_7 ام تا حرف formula_8 ام را با formula_9 نشان می‌دهیم. در این صورت آرایه ال‌سی‌پی formula_10 یک آرایه با اندازهٔ formula_11 از اعداد صحیح است که formula_12 تعریف نشده‌است و formula_13 به ازای هر formula_14 نشان‌دهندهٔ جایگاه شروع formula_7 امین کوچک‌ترین پسوند رشتهٔ formula_6 از نظر لغتنامه‌ای است، پس formula_17 طول بلندترین پیشوند مشترک formula_18 امین و formula_7 امین پسوند رشتهٔ formula_6 از نظر لغتنامه‌ای است (formula_21 را در نظر بگیرید:
و آرایهٔ پسوندی مرتب‌شدهٔ متناظر با آن:
پسوندهای رشتهٔ formula_6 که به صورت ستونی و مرتب‌شده نوشته شده‌اند: آرایهٔ ال‌سی‌پی با مقایسهٔ پسوندهای متوالی از نظر لغت‌نامه‌ای برای مشخص کردن بزرگ‌ترین پیشوند مشترک آن‌ها محاسبه می‌شود: برای مثال، formula_23 طول بزرگ‌ترین پیشوند مشترک بین formula_24 و formula_25 یعنی رشته formula_26 است.
فرض کنید می‌خواهیم تعداد رخدادهای یک الگوی formula_27 (به طول formula_28) در یک متن formula_29 (به طول formula_30) را بیابیم. می‌توان با دو بار استفاده از جستجوی دودویی، مکان اولین و آخرین رخداد formula_27 در آرایه پسوندی formula_29 را بدست آورد و در نتیجه تعداد رخدادهای رشته formula_27 در متن formula_29 بدست می‌آید. در هر کدام از جستجوهای دودویی formula_35 مقایسه نیاز است و با توجه به اینکه در هر مقایسه رشتهٔ formula_27 را با یکی از عناصر آرایه پسوندی مقایسه می‌کنیم، در بدترین حالت ممکن است نیاز به مقایسهٔ کامل دو رشته باشد که به معنی مقایسهٔ formula_28 کاراکتر است؛ بنابراین زمان اجرای این الگوریتم از formula_38 است.
با استفاده از آرایه ال‌سی‌پی، الگوریتمی با زمان اجرای formula_39 ارائه می‌دهیم. به ازای هر formula_40، formula_41 را برابر formula_42 تعریف می‌کنیم؛ در واقع formula_41 برابر formula_7امین کوچک‌ترین پسوند formula_6 است. ابتدا فرض کنیم به ازای هر formula_46 مقدار formula_47 از قبل محاسبه شده‌است. در هر مرحله از جستجوی دودویی، یک بازه formula_48در آرایه پسوندی به همراه نقطه میانی آن formula_49 را در نظر می‌گیریم. سپس با مقایسهٔ formula_27 وformula_51 مشخص می‌کنیم که جستجو را در بازهٔ formula_52 ادامه دهیم یا بازهٔ formula_53. فرض کنیم formula_27 بزرگتر از formula_51 باشد و اولین حرفی از formula_27 و formula_51 که متفاوت اند حرف formula_58 ام باشد؛ یعنی formula_59. پس در مرحلهٔ بعدی جستجو، بازه formula_53 با نقطه میانی formula_61 را در نظر می‌گیریم. با توجه به فرضی که کردیم، مقدار formula_62 از قبل محاسبه شده‌است و در زمان formula_63 قابل دسترس است. سه حالت ممکن است پیش بیاید:
در الگوریتم بالا هر کاراکتر از رشتهٔ formula_27 حداکثر یک بار با کاراکترهای متن formula_29 مقایسه می‌شود؛ بنابراین زمان اجرای این الگوریتم formula_39 است.
اما فرض کرده بودیم به ازای هر formula_46 مقدار formula_47 از قبل محاسبه شده‌است. توجه کنیم که همهٔ بازه‌های ممکن formula_48 در الگوریتم جستجوی دودویی ظاهر نمی‌شوند. به ازای هر نقطهٔ formula_104، دقیقاً یک بازه با نقطهٔ میانی formula_49 وجود دارد که در الگوریتم جستجوی دودویی ممکن است ظاهر شود. این بازه را با formula_106 نشان می‌دهیم و به ازای هر formula_104 تعریف می‌کنیم: با توجه به الگوریتم گفته شده، فقط به مقادیر آرایه‌های formula_110 و formula_111 نیاز داریم که حافظه‌ای از formula_112 اشغال می‌کنند. هم‌چنین از روی آرایه ال‌سی‌پی و در زمان formula_112 می‌توان مقادیر formula_110 و formula_111 را محاسبه کرد.
در سال ۱۹۹۰ Manber و Myers الگوریتمی از formula_116 دادند که در کنار آرایه پسوندی، آرایه ال‌سی‌پی را نیز محاسبه می‌کند. در سال ۲۰۰۳ الگوریتمی از formula_112 برای ساختن هم‌زمان آرایه پسوندی و آرایه ال‌سی‌پی ارایه شد.
در سال ۲۰۰۱ الگوریتمی ارایه شد که در formula_112 آرایه ال‌سی‌پی را از روی متن و آرایه پسوندی محاسبه می‌کند.