12040 - Again Lucky Numbers

[brainless_the_swiss]

Dear all,

It would be great if someone helps me with this challenge :
http://uva.onlinejudge.org/index.php?op ... oblem=3191

When the number M cannot "overlap" itself, it is not a big deal to compute it recursively.
By "overlapping itself", here is an example :

If M=1212, then the number "121212" contains M both at its beginning and at its end. If M=12312, then "12312312" is another string containing twice M overlapping itself. The overlap is the substring "12" in the middle. M=123 is a case where M cannot overlap itself.

The tricky cases are when M can overlap itself.

I have looked for similar situations on other topics, like 10722 - Super lucky numbers and 10712 - Count the numbers:
http://online-judge.uva.es/board/viewto ... ky+numbers

Any little hint will allow me to move forward.

Thanks in advance for your help !

[evaaaaaaaan]

Dear all,

It would be great if someone helps me with this challenge :
http://uva.onlinejudge.org/index.php?op ... oblem=3191

When the number M cannot "overlap" itself, it is not a big deal to compute it recursively.
By "overlapping itself", here is an example :

If M=1212, then the number "121212" contains M both at its beginning and at its end. If M=12312, then "12312312" is another string containing twice M overlapping itself. The overlap is the substring "12" in the middle. M=123 is a case where M cannot overlap itself.

The tricky cases are when M can overlap itself.

I have looked for similar situations on other topics, like 10722 - Super lucky numbers and 10712 - Count the numbers:
http://online-judge.uva.es/board/viewto ... ky+numbers

Any little hint will allow me to move forward.

Thanks in advance for your help !

this problem can be solved using dp + some prefix matching technique