ابتدا توابع کتابخانه استاندارد را بررسی میکنیم سپس کاربردهای برنامهریزی پویا در پردازش رشته را مرور میکنیم و در آخر به ساختماندادههای پیشرفته مربوط به رشتهها میپردازیم.
در $C++$ کتابخانه استاندارد رشته $string.h$ است که نوع رشته پویا و توابع زیررشته و جستجوی خطی رشته را شامل میشود. عملگرهای سربارگذاری شده آن شامل ورودی و خروجی، خواندن یک خط، چسباندن رشتهها و جابهجایی رشتهها هستند.
کتابخانه $algorithm.h$ توابع جستجوی خطی، مرتبسازی الفبایی، جایگشت و … را دارد که برای رشتهها هم قابل استفاده است.
در قسمت برنامهریزی پویا مثالهایی از پردازش رشته مانند بزرگترین زیررشته مشترک و تبدیل رشتهها آوردیم. مسألهی دیگری که معمولاً در این زمینه معرفی میشود رشتههای آینهای هستند، یعنی رشتههایی که وقتی از آخر به اول آنها را بخوانیم خودشان میشوند.
مسألهی پیدا کردن طولانیترین زیررشتهی آینهای را میتوان با برنامهریزی پویا به این صورت حل کرد که به ازای هر بازه، طولانیترین زیررشتهی آینهای آن را نگه داریم. با این کار کافی است که دو حرف یکسان به دو طرف این رشته اضافه شود که رشته آینهای با طول بیشتری بدهد. حالت پایهی این رشته میتواند رشته ۲ حرفی یا یک حرفی باشد.
در این قسمت کاربردهای ساختمان دادههای پیشرفته روی رشتهها را میآوریم.
درختی است که در آن پسوندهای یک رشته ذخیره شدهاند، به طوری که هر برگ آن شامل یک پسوند رشته ورودی است و گرههای میانی جایی هستند که دو پسوند در ادامه با هم تفاوت پیدا میکنند. برای استفاده از این ساختمان داده باید یک علامت پایان رشته قرار بدهیم (معمولاً $\$$).
کاربرد آن در مسایل زیر است:
نسخهی آرایهای درخت پسوندی است که پیادهسازی آن بسیار آسانتر است. در این آرایه اندیس آرایهای از رشتهها نگهداری میشود که در آن پسوندهای رشته ورودی به ترتیب الفبایی قرار دارند. یک رأس درخت پسوندی، معادل یک بازه در آرایه پسوندی است.