پاسخ پرسش CF-197-C
Codeforces / Contest 197 / Problem C : Lexicographically Maximum Subsequence
صورت اصلی سوال :http://codeforces.com/contest/197/problem/C
ترجمه :
رشته s ار حروف کوچک انگلیسی داده شده ، بزرگترین زیر رشته lexicographically این رشته را بیابید .
یک زیر رشته از s تعدادی از حروف s است که به ترتیب ظاهر شدنشان در رشته در زیر رشته می آیند .
یک زیر رشته x از زیر رشته y بزرگتر است اگر اندازه x بزرگتر از y باشد در حالی که همه کاراکتر های ۱ تا |y| در دو رشته مساوی باشند یا اینکه یک مقدار r وجود داشته باشد به طوری که همه ی کاراکت های ۱ تا r در دو رشته برابر باشند و کاراکتر r+1 ام x بزرگتر از کارکتر r+1 ام y باشد .
ورودی :
در تنها خط ورودی رشته s به شما داده می شود .
طول رشته s از 105 تجاوز نمی کند .
خروجی :
بزرگترین زیر رشته lexicographically رشته s را در خروجی چاپ کنید .
شرح راه حل :
از یک پشته (stack) کمک می گیریم و با یک بار پیمایش رشته s و یک ایده حریصانه به پرسش در زمانی خطی پاسخ می دهیم .
یک پشته به نام ans در نظر بگیرید . در هر مرحله که روی کاراکتر i ام هستیم در صورتی که کاراکتر i ام s از آخرین عضو در پشته کوچک تر است آن را به انتهای پشته اضافه می کنیم و در غیر این صورت تا زمانی که آخرین عضو ans از این کاراکتر کوچکتر شود یا اینکنه اندازه ans برابر با صفر شود ، از انتهای پشته بیرون می کنیم .(چرا ؟)
در نهایت مفداری که در پشته ans هست ، پاسخ پرسش ، یعنی بزرگترین زیر رشته lexicographically از رشته s است .
