Question entretien chez 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.

Utilisateur anonyme

19 janv. 2011

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

Utilisateur anonyme

5 févr. 2011

Use Boyer-moore algorithm.

Utilisateur anonyme

23 févr. 2011

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

Utilisateur anonyme

13 mars 2011

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

Utilisateur anonyme

11 déc. 2011

Use Robin-karp or KMP algorithm