To Peter: No. After the onsite, I was given an extra interview about culture fit. So I guess I didn't satisfy the interviewer in the culture fit round, not the technical round. I felt I was doing well in the extra interview. But I didn't get the offer. The recruiter didn't give me feedback about why I didn't get the offer.

Thanks S Sven. Your feedback is really appreciated. Thanks for taking out time to reply.

KMP is pretty hard to remember, why didn't you try to go with Rabin-Karp or Boyer-Moore?

For the regular expression question, what is your solution? There seems to be at least two solutions. One is based on dynamic programming, and the other based on non-determinstic automata. I'm not quite sure which sotluion is better to take at the interview.