title: KMP algorithm worst case analysis
body: <p>I can't understand how KMP maintains O(m+n). I'm looking for a pattern &quot;aaaab&quot; in &quot;aaaaaaaaaa...&quot;.</p>
  <ul>
  <li>pattern : aaaab (length n)</li>
  <li>string : aaaaaaaaaa... (length m)</li>
  </ul>
  <p>Then the prefix table would be</p>
  <blockquote>
  <p>aaaab</p>
  <p>01230</p>
  </blockquote>
  <p>Every time mismatch happens on 'b', it's prefix length is always 0. So the pattern shifts only one step right.</p>
  <blockquote>
  <p>aaaaaaaaaa...</p>
  <p>aaaab</p>
  <p>aaaaaaaaaa...</p>
  <p>_aaaab</p>
  <p>aaaaaaaaaa...</p>
  <p>__aaaab</p>
  </blockquote>
  <p>And for every trial, I need to compare full n times since mismatch happens at the very last 'b'. Thus it still requires O(m*n) comparisons.</p>
  <p>Can anyone explain how KMP get O(m+n) for me? Thanks in advance.</p>