مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.
====== پردازش رشته ======
ابتدا توابع کتابخانه استاندارد را بررسی می‌کنیم سپس کاربردهای [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]] در پردازش رشته را مرور می‌کنیم و در آخر به ساختمان‌داده‌های پیشرفته مربوط به رشته‌ها می‌پردازیم.
===== کتابخانه استاندارد =====
در $C++$ کتابخانه استاندارد رشته $string.h$ است که نوع رشته پویا و توابع زیررشته و جستجوی خطی رشته را شامل می‌شود. عملگرهای سربارگذاری شده آن شامل ورودی و خروجی، خواندن یک خط، چسباندن رشته‌ها و جابه‌جایی رشته‌ها هستند.

[[http://www.cplusplus.com/reference/string/string/|توابع کتابخانه استاندارد رشته]]

کتابخانه $algorithm.h$ توابع جستجوی خطی، مرتب‌سازی الفبایی، جایگشت و ... را دارد که برای رشته‌ها هم قابل استفاده است.

[[http://www.cplusplus.com/reference/algorithm/|توابع کتابخانه استاندارد الگوریتم]]
===== برنامه‌ریزی پویا در پردازش رشته =====
در قسمت [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]] مثالهایی از پردازش رشته مانند بزرگترین زیررشته مشترک و تبدیل رشته‌ها آوردیم. مسأله‌ی دیگری که معمولاً در این زمینه معرفی می‌شود رشته‌های آینه‌ای هستند، یعنی رشته‌هایی که وقتی از آخر به اول آنها را بخوانیم خودشان می‌شوند.

مسأله‌ی پیدا کردن طولانی‌ترین زیررشته‌ی آینه‌ای را می‌توان با [[الگوریتم:برنامه‌ریزی_پویا|برنامه‌ریزی پویا]] به این صورت حل کرد که به ازای هر بازه، طولانی‌ترین زیررشته‌ی آینه‌ای آن را نگه داریم. با این کار کافی است که دو حرف یکسان به دو طرف این رشته اضافه شود که رشته آینه‌ای با طول بیشتری بدهد. حالت پایه‌ی این رشته می‌تواند رشته ۲ حرفی یا یک حرفی باشد.
===== ساختمان داده‌های پردازش رشته =====
در این قسمت کاربردهای ساختمان داده‌های پیشرفته‌ روی رشته‌ها را می‌آوریم.
==== درخت پسوندی ====
درختی است که در آن پسوندهای یک رشته ذخیره شده‌اند، به طوری که هر برگ آن شامل یک پسوند رشته ورودی است و گره‌های میانی جایی هستند که دو پسوند در ادامه با هم تفاوت پیدا می‌کنند. برای استفاده از این ساختمان داده باید یک علامت پایان رشته قرار بدهیم (معمولاً $\$$).

کاربرد آن در مسایل زیر است:
  * پیدا کردن تکرارهای یک رشته در رشته دیگر در زمان خطی بر حسب طول رشته مورد جستجو و تعداد تکرارهای آن در رشته اصلی: برای این کار کافی است گره‌ای میانی را پیدا کنیم که رشته مورد جستجو در آن است و رشته‌های متناظر این گره جوابهای مسأله هستند.
  * پیدا کردن طولانی‌ترین رشته تکرار شده در زمان خطی بر حسب تعداد حرفهای رشته: برگ با بیشترین عمق جواب است.
  * طولانی‌ترین زیررشته مشترک: درخت پسوندی را برای پسوندهای دو رشته داده شده می‌سازیم ولی آنها را علامت می‌گذاریم. گره با بیشترین عمق که شامل هر دو رشته باشد جواب است.

[[http://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D9%BE%D8%B3%D9%88%D9%86%D8%AF%DB%8C|مطالب بیشتر در مورد درخت پسوندی]]
==== آرایه پسوندی ====
نسخه‌ی آرایه‌ای درخت پسوندی است که پیاده‌سازی آن بسیار آسان‌تر است. در این آرایه اندیس آرایه‌ای از رشته‌ها نگه‌داری می‌شود که در آن پسوندهای رشته ورودی به ترتیب الفبایی قرار دارند. یک رأس درخت پسوندی، معادل یک بازه در آرایه پسوندی است.

[[http://en.wikipedia.org/wiki/Suffix_array|مطالب بیشتر در مورد آرایه پسوندی]]
مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه
