آرایه ال‌سی‌پی

در علوم رایانه، **آرایه طولانی‌ترین پیشوند مشترک ([[آرایه (ساختار داده)|آرایه]] ال‌سی‌پی)**  یک داده‌ساختار کمکی برای آرایه پسوندی است. در این آرایه، طولانی‌ترین پیشوند مشترک بین هر دو پسوند متوالی موجود در آرایه پسوندی ذخیره می‌شود.

## تاریخچه
آرایه ال‌سی‌پی توسط Udi Manber و Gene Myers در سال ۱۹۹۰ به همراه آرایه پسوندی و برای بهبود سرعت الگوریتم جستجوی الگو در متن ارائه شد.

## تعریف
فرض کنیم A آرایه پسوندی رشته S=S[1]S[2]...S[n] بوده و lcp(v,w) نشان‌دهندهٔ طولانی‌ترین پیشوند مشترک رشته‌های v و w باشد. هم چنین زیررشتهٔ S از حرف i ام تا حرف j ام را با S[i,j] نشان می‌دهیم. در این صورت آرایه ال‌سی‌پی H[1,n] یک آرایه با اندازهٔ n از اعداد صحیح است که H[1] تعریف نشده‌است و H[i]=lcp(S[A[i-1],n], S[A[i],n]) به ازای هر 1. با توجه به اینکه A[i] نشان‌دهندهٔ جایگاه شروع i امین کوچک‌ترین پسوند رشتهٔ S از نظر لغتنامه‌ای است، پس H[i] طول بلندترین پیشوند مشترک i-1 امین و i امین پسوند رشتهٔ S از نظر لغتنامه‌ای است (1).

## مثال
رشتهٔ S=banana\$ را در نظر بگیرید:

و آرایهٔ پسوندی مرتب‌شدهٔ متناظر با آن:

پسوندهای رشتهٔ S که به صورت ستونی و مرتب‌شده نوشته شده‌اند:

آرایهٔ ال‌سی‌پی با مقایسهٔ پسوندهای متوالی از نظر لغت‌نامه‌ای برای مشخص کردن بزرگ‌ترین پیشوند مشترک آن‌ها محاسبه می‌شود:

برای مثال، H[4]=3 طول بزرگ‌ترین پیشوند مشترک بین S[A[3],7] = S[4,7] = ana\$ و S[A[4],7] = S[2,7] = anana\$ یعنی رشته ana است.

## استفاده از آرایه ال‌سی‌پی برای جستجوی یک الگو در متن
فرض کنید می‌خواهیم تعداد رخدادهای یک الگوی P (به طول m) در یک متن T (به طول N) را بیابیم. می‌توان با دو بار استفاده از جستجوی دودویی، مکان اولین و آخرین رخداد P در آرایه پسوندی T را بدست آورد و در نتیجه تعداد رخدادهای رشته P در متن T بدست می‌آید. در هر کدام از جستجوهای دودویی O(logN) مقایسه نیاز است و با توجه به اینکه در هر مقایسه رشتهٔ P را با یکی از عناصر آرایه پسوندی مقایسه می‌کنیم، در بدترین حالت ممکن است نیاز به مقایسهٔ کامل دو رشته باشد که به معنی مقایسهٔ m کاراکتر است؛ بنابراین زمان اجرای این الگوریتم از O(m\times logN) است.

با استفاده از آرایه ال‌سی‌پی، الگوریتمی با زمان اجرای O(m+logN) ارائه می‌دهیم. به ازای هر 1\le i \le n، S_i را برابر S[A[i],n] تعریف می‌کنیم؛ در واقع S_i برابر iامین کوچک‌ترین پسوند S است. ابتدا فرض کنیم به ازای هر 1 \le i,j \le n مقدار lcp(S_i, S_j) از قبل محاسبه شده‌است.
در هر مرحله از جستجوی دودویی، یک بازه (L,...,R)در آرایه پسوندی به همراه نقطه میانی آن M را در نظر می‌گیریم. سپس با مقایسهٔ P وS_M مشخص می‌کنیم که جستجو را در بازهٔ (L,...,M) ادامه دهیم یا بازهٔ (M,...,R). فرض کنیم P بزرگتر از S_M باشد و اولین حرفی از P و S_M که متفاوت اند حرف k+1 ام باشد؛ یعنی lcp(P, S_M)=k. پس در مرحلهٔ بعدی جستجو، بازه (M,...,R) با نقطه میانی M' را در نظر می‌گیریم. با توجه به فرضی که کردیم، مقدار lcp(S_M, S_{M'})=k' از قبل محاسبه شده‌است و در زمان O(1) قابل دسترس است. سه حالت ممکن است پیش بیاید:
* حالت ۱: k، یعنی طولانی‌ترین پیشوند مشترک P و S_M کمتر از طولانی‌ترین پیشوند مشترک S_M و S_{M'} است؛ بنابراین k+1 امین حرف S_M و S_{M'} یکسان است و چون P>S_M در نتیجه P>S_{M'}. بنابراین جستجو را در بازهٔ (M',...,R) ادامه می‌دهیم.
* حالت ۲: k>k'، یعنی P و S_M پیشوند مشترک بیشتری نسبت به S_M و S_{M'} دارند. با توجه به اینکه آرایه پسوندی با ترتیب لغت‌نامه‌ای مرتب شده‌است، پس S_{M'}>S_M. از آنجا که اولین حرفی که S_M و S_{M'} در آن متفاوت اند حرف k'+1 ام است و رشته‌های P و S_M در این حرف یکسان اند، پس S_{M'}>Pو در نتیجه جستجو در بازه (M,...,M') ادامه می‌یابد.
* حالت ۳: k=k'، یعنی رشته‌های S_M و S_{M'} در k حرف اول با رشتهٔ P یکسان اند. برای مقایسه رشته‌های S_{M'} و P، این دو رشته را از حرف k+1 ام به بعد مقایسه می‌کنیم تا به اولین حرف متفاوت برسیم. به این ترتیب در مرحلهٔ بعدی الگوریتم جستجوی دودویی، مقدار lcp(P, S_{M'}) را داریم و می‌توانیم به همین صورت الگوریتم جستجوی P را ادامه دهیم.

در الگوریتم بالا هر کاراکتر از رشتهٔ P حداکثر یک بار با کاراکترهای متن T مقایسه می‌شود؛ بنابراین زمان اجرای این الگوریتم O(m+logN) است.

اما فرض کرده بودیم به ازای هر 1 \le i,j \le n مقدار lcp(S_i, S_j) از قبل محاسبه شده‌است. توجه کنیم که همهٔ بازه‌های ممکن (L,...,R) در الگوریتم جستجوی دودویی ظاهر نمی‌شوند. به ازای هر نقطهٔ 2 \le M \le n-1، دقیقاً یک بازه با نقطهٔ میانی M وجود دارد که در الگوریتم جستجوی دودویی ممکن است ظاهر شود. این بازه را با (L_M, M, R_M) نشان می‌دهیم و به ازای هر 2 \le M \le n-1 تعریف می‌کنیم:
* Llcp[M]=lcp(S_{L_M}, S_M)
* Rlcp[M]=lcp(S_M, S_{R_M})
با توجه به الگوریتم گفته شده، فقط به مقادیر آرایه‌های Llcp و Rlcp نیاز داریم که حافظه‌ای از O(N) اشغال می‌کنند. هم‌چنین از روی آرایه ال‌سی‌پی و در زمان O(N) می‌توان مقادیر Llcp و Rlcp را محاسبه کرد.

## ساختن آرایه ال‌سی‌پی
در سال ۱۹۹۰ Manber و Myers الگوریتمی از O(NlogN) دادند که در کنار آرایه پسوندی، آرایه ال‌سی‌پی را نیز محاسبه می‌کند. در سال ۲۰۰۳ الگوریتمی از O(N) برای ساختن هم‌زمان آرایه پسوندی و آرایه ال‌سی‌پی ارایه شد.

در سال ۲۰۰۱ الگوریتمی ارایه شد که در O(N) آرایه ال‌سی‌پی را از روی متن و آرایه پسوندی محاسبه می‌کند.

## جستارهای وابسته
* آرایه پسوندی
* الگوریتم جستجوی رشته

## منابع

رده:آرایه
رده:الگوریتم‌ها
رده:الگوریتم‌های جستجوی رشته
رده:ساختارهای داده‌های رشته‌ای
رده:ساختمان داده