This follows my earlier post on interview questions and answers:
Question: If you are given a string of length N and M strings each of length L, How will you find that each of the M strings occurred in the larger string ?
Answer: There are several approaches to this problem.
The first approach is to iterate for each of the M strings to see if it occurs in the original string.
For each pattern that we match, we can do one of the following:
1) Brute force method : Iterate through each character of the original string to see if its the start of the pattern. For the length of the pattern, match the subsequent characters to see if the pattern exists.
2) Finite - automata: This is an improvement on the pattern match part. We build a string matching automaton that lets us complete the pattern match in linear time.
3) All match at once: This is an improvement on the iteration of all the patterns. Instead of iterating over each of them one by one, each pattern match and automaton progress can be stored as the characters of the original string are iterated.
Question: If you are given a string of length N and M strings each of length L, How will you find that each of the M strings occurred in the larger string ?
Answer: There are several approaches to this problem.
The first approach is to iterate for each of the M strings to see if it occurs in the original string.
For each pattern that we match, we can do one of the following:
1) Brute force method : Iterate through each character of the original string to see if its the start of the pattern. For the length of the pattern, match the subsequent characters to see if the pattern exists.
2) Finite - automata: This is an improvement on the pattern match part. We build a string matching automaton that lets us complete the pattern match in linear time.
3) All match at once: This is an improvement on the iteration of all the patterns. Instead of iterating over each of them one by one, each pattern match and automaton progress can be stored as the characters of the original string are iterated.
No comments:
Post a Comment