پاسخ پرسش CF-169-C

سه شنبه, ۸ فروردين ۱۳۹۱، ۱۲:۲۳ ب.ظ

Codeforces / Contest 169 / Porblem C : Substring and Subsequence

صورت اصلی سوال : http://codeforces.com/contest/169/problem/C

ترجمه :

دو رشته با نام های s و t داریم.

می خواهیم تعداد زوج های x و y را پیدا کنیم که دارای شرایط زیر باشند :

x زیر رشته ی s باشد
y زیر مجموعه ی t باشد
مقادیر x و y یکسان باشند

توجه کنید که تعریف زیر مجموعه و زیر رشته کاملا مجزا از هم است .

زیر رشته : یعنی بخشی از یک رشته به صورت پیوسته (از کاراکتر i ام تا کاراکتر j ام).

زیر مجموعه : یعنی تعدادی از کاراکتر های یک رشته (که البته می تواند شامل کاراکتر تکراری نیز باشد)

توجه کنید که در زیر مجموعه حروف زیر مجموعه ترتیب قرار گرفتن خود در t را حفظ می کنند.

به عنوان مثال"forces" یک زیر رشته از رشته ی "codeforces" است (از کاراکتر 5ام تا کاراکتر 10ام)

و "codercs" یک زیر مجموعه از رشته ی "codeforces" است (در حالی که یک زیر شته نیست)

ورودی :

ورودی شامل دو خط می شود

خط اول رشته ی s و خط دوم رشته ی t که هر دو تنها شامل حروف کوچک انگلیسی هستند .

طول هر دو رشته بزرگتر از 1 و کوچکتر از 5000 است .

خروجی :

در تنها خط خروجی پاسخ پرسش یعنی تعداد زوج های x و y با شرایط ذکر شده را در مد 1e9+7 چاپ کنید .

__________________________________________
الگوریتم :

در ابتدا شاید استفاده از یک روش جستجوی کامل (brute force) درست به نظر بیاید ولی در بهترین حالت این روش از یا خواهد بود که در محدودیت زمان 2 ثانیه قابل اجرا نیست.

پس از روش برنامه ریزی پویا سوال را حل می کنیم .

آرایه ans را در نظر بگیرید . هر درایه نشان دهنده ی تعداد زوج های x و y است به طوری که x زیر رشته ای از s که آخرین کاراکتر آن کاراکتر i ام s است است و y نیز زیر مجموعه ای از j کاراکتر اول رشته ی t است .