- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
حسینقلی که در کلانتری کار می‌کند و کل ساعت کاری را با یک دزدی کلان سر و کله زده است، بعد از یک روز طولانی به خانه بازگشته است. ناگهان بر روی تخته تعداد زیادی $\text{kalantar}$ و $\text{kalan}$ و $\text{tar}$ و اسپیس (فضاهای خالی) می‌بیند. با توجه به اینکه ممکن است این کار تهدید دزدها باشد، قرار است این متن را بررسی کند تا زمانی که بررسی به پایان برسد.
در هر مرحله از بررسی، حسینقلی به دنبال زیررشته‌های برابر با $\text{kalan}$ که دقیقاً بعد از آن‌ها و یا بعد از تعدادی فضای خالی $\text{tar}$ نوشته شده باشد می‌گردد و سپس تمام این $\text{kalan}$های پیدا شده با $\text{tar}$های بعد آن‌ها را با فضای خالی بینشان (در صورت وجود) همزمان پاک می‌کند.
برای مثال متن زیر در هر مرحله بررسی به متن خط بعد از آن تبدیل می‌شود، تا جایی که بعد از دو مرحله در ادامه‌ی هیچ زیر رشته $\text{kalan}$ رشته $\text{tar}$ مشاهده نمی‌شود. $$\text{kalan tar tartar kalankalantar tar kalan kalantar tar}$$ $$\text{ tartar kalan tar kalan tar}$$ $$\text{ tartar }$$
می‌دانیم هر کلانتری که حسینقلی پاک می‌کند یک واحد تهدید و هر کلان تر که تعدادی فضای خالی بین آن‌ها باشد یک واحد گمراهی است.
برای کمک به حسینقلی با گرفتن متن روی تخته، تعداد مراحل بررسی را چاپ کنید و در هر مرحله تعداد تهدیدها و گمراهی ها را به او هشدار دهید.
ورودی
در تنها خط ورودی، رشته $s$ که نشاندهنده متن روی تخته است به شما ورودی داده می‌شود. $$ 1 \le |s| \le 10^6$$
خروجی
در خط اول خروجی، تعداد مراحل بررسی متن توسط حسینقلی را خروجی دهید.
سپس در خطوط بعدی، در هر خط به ترتیب تعداد تهدیدهای یک بررسی و سپس تعداد گمراهی‌های آن بررسی را خروجی دهید. مراحل بررسی را به ترتیب از مرحله اول تا آخر خروجی دهید.
مثال‌ها
ورودی نمونه ۱
kalankalan tar kalankalantar tar kalantartar tar
خروجی نمونه ۱
3
2 1
0 1
0 1
متن اولیه نمونه ۱ به شرح زیر است:
$$\text{kalankalan tar kalankalantar tar kalantartar tar}$$
در مرحله اول زیررشته‌های kalantar، kalantar و kalan tarپاک می‌شوند.
$$\text{kalan kalan tar tar tar}$$
در مرحله دوم زیررشته kalan tar پاک می‌شود.
$$\text{kalan tar tar}$$
در مرحله سوم زیررشته kalan tar پاک می‌شود.
$$\text{ tar}$$
ارسال پاسخ برای این سؤال