The KMP paper is "Fast Pattern Matching In Strings", which cites Cook's "Linear time simulation of deterministic two-way pushdown automata". The former has a neat history section that gives a little more detail than the interview.