Hello, today took place round #313. I have recently read some articles regarding hashing and how useful they can be to compare to strings really fast. When I read problem D (Equivalent Strings), I came up with a possible solution using DP and Hashing. It took me quite some time to get it to work properly, but sadly I got a TLE veredict after the final tests came through. This is my solution: http://mirror.codeforces.com/contest/560/submission/12189499.

After the contest, I managed to make it work slightly faster, but it only got AC after changing the recursion order, I know this in fact affects the running time of my solution. But I still haven't been able to figure the actual time complexity of this solution. I used four states representing the segment of string A and B we are currently checking if they are equivalent or not. I had to use a map, in order to keep a memo for the states already calculated. With the help of hashing, I believe the string comparisons could be done quite fast.

Cheers, Angel