Show the index where the pattern first appears.
Acceptance criteria
- 1.#out should show at 6.
DSA Tutorial · Strings
Practice: String Matching: KMP and Rabin-Karp
These 10 tasks go with the String Matching: KMP and Rabin-Karp chapter. 5 of them ask you to build something small from scratch; 5 give you code that is already broken and ask you to work out why. Set aside about 90 minutes for the whole set, though you can do them in any order.
Nothing here is marked by a person. When you press Submit, the editor checks your code against the points listed under each task and tells you straight away what passed and what didn't (you need a free account to submit). If you get stuck, there are hints, and a worked solution once you've had a go. The first 2 tasks are free; the rest are part of the practice plan.
If it's been a while since you read the chapter, here is how it starts: “Searching for a substring is O(n × m) if you do the obvious thing. Two classic algorithms get it to O(n + m), each by never throwing away what the previous comparison already told you.” .