მსგავსება

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 32 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: CEOI, 2011, საცდელი ტური


ბაიტმენი მუშაობს გამოთვლითი ბიოლოგიის მკვლევარ გუნდში. მისი ძირითადი საქმეა ალგორითმების შემუშავება, რომლებიც სტრინგებს, ნიმუშებსა და ტექსტებს ეხება. მისი მიმდინარე დავალებაა, შეიმუშავოს მექანიზმი, რომელიც გამოთვლის მსგავსებას ნიმუშსა და ტექსტს შორის.

ნიმუში და ტექსტი ბევრნაირად შეიძლება დავაწყოთ ისე, რომ ნიმუშის თითოეულ სიმბოლოს, პოზიციურად ტექსტში ერთი სიმბოლო შეესაბამებოდეს, თანაც გამოტოვებების გარეშე, ანუ ნიმუში უნდა შევუსაბამოთ ტექსტის უწყვეტ ნაწილს (სეგმენტს), რომლის სიგრძეც ნიმუშის სიგრძეს ემთხვევა. თითოეული ასეთი დაწყობის დროს, დავითვალოთ ნიმუშის რამდენი სიმბოლო ემთხვევა თავის შესაბამის სიმბოლოს ტექსტში. ამ რიცხვების ჯამს კი დავარქვათ ნიმუშისა და ტექსტის მსგავსება. ქვემოთ მოცემულია მსგავსების გამოთვლა, როცა ნიმუშია abaab და ტექსტია aababacab.

aababacab        aababacab         3+3+1+3+2=12

abaab____        a##ab____         3 

_abaab___        _aba##___         3

__abaab__        __###a#__         1

___abaab_        ___aba##_         3

____abaab        ____###ab         2

            ბაიტმენმა უკვე გაამზადა გრაფიკული ინტერფეისი მექანიზმისთვის. თქვენი დავალებაა დაწეროთ კოდი, რომელიც გამოითვლის მსგავსებას ნიმუშსა და ტექსტს შორის.

            ინფუთი შედგება ორი ხაზისგან, ორივე წარმოადგენს არაცარიელ სტრინგს, რომელიც პატარა ლათინური ასოებისგან შედგება. პირველი არის ნიმუში, ხოლო მეორე - ტექსტი. ჩათვალეთ რომ ნიმუშის სიგრძე არ აღემატება ტექსტის სიგრძეს და ტექსტის სიგრძე არ აღემატება ორ მილიონს.

            აუთფუთი უნდა შეიცავდეს ერთადერთ ხაზს - მსგავსებას ნიმუშსა და ტექსტს შორის.




მაგალითები

შესატანი მონაცემები
abaab aababacab დაკოპირება
გამოსატანი მონაცემები
12 დაკოპირება