Pergunta de entrevista da empresa Amazon: Write a function to search for a string within another string. Analyze it's complexity, and propose optimizations.

Amazon

Write a function to search for a string within another string. Analyze it's complexity, and propose optimizations.

Sigiloso

19 de jan. de 2011

Represent the string in Suffix Tree and u can find the pattern in O(m) time.

Sigiloso

5 de fev. de 2011

Use Boyer-moore algorithm.

Sigiloso

23 de fev. de 2011

@jimmy thanks http://www.movsd.com/bm.htm

Sigiloso

13 de mar. de 2011

I wonder if you had to code BM algorithm during the interview. That would be... hard...

Sigiloso

11 de dez. de 2011

Use Robin-karp or KMP algorithm