Morris Algorithm



Good Example to remember

pattern: ABCDABD




next table:

ABCDABD for D you have 2 since the string your are looking for is

ABCDAB ABCCAB doesn’t make 3

How to build next:

1. first two place is special, then left move by 1 then keep search

2. keep searching until equal

Then with the next array how to match

Both two string pointer should be valid, finally the target string should be iter throughed totally


  1. basic backpack question, use reachable method to solve it

    pay attention to the derive operation, even some new added number has no help, the place can still be true because of the derive operation

  2. backpack with value, same solution

    also should pay attention to the derive relationship among them

  3. Minimum Adjustment Cost

    1. Firstly, we can use recursion to solve it

      cannot use the simple cache, since the parameter not only has included current index, but also some precondition
      Even though lots of continue to jump through, but still lots of repeating computation

    2. Secondly, the dp just layout all the memory footprint using lowerbound, and upperbound

    3. Finally the space complexity can still be reduced