ADS1: Naive exact matching

[@bonbonpony]

If this is the naïve algorithm, then what are better ways to do it?

[@wejesuss-1104]

boyer-moore

[@sublime5969]

I highly appreciate your effort in the videos. Thank you! In the question: "How many character comparisons in this example?" Formula for the minimum is y - x + 1, I therefore got 32 as the minimum character comparisons. i.e 35 - 4 + 1 I got maximum character comparisons as 128 : x(y - x + 1) = 4 (35 - 4 + 1) = 128 I got 6 matches: w, wo, (in would) and w, wo, wor, word (in word) Sir, Could you please clarify how you achieved 41 minimum character comparisons and 40 mismatches

[@Rcrdslns]

@sublime5969 In the presented case, the blank spaces are also counted, which are the 9 characters you are missing in your count. Hope this helps

[@MikeVella]

isn't it 45 rather than 46 comparisons? aside from the two w characters there are only 4 other characters being matched (o and ord) so the number of comparisons should be 4 more than the worst case.

[@khalidakram]

excellent

[@ChimeraGilbert]

Couldn't you achieve the naive exact matching algorithm more efficiently by avoiding a double for-loop? Like this: `def naive_2(p, t): occurences = [] p_len = len(p) for i in range(len(t) - p_len + 1): if t[i:i+p_len] == p: occurences.append(i) return occurences`

[@seifeldineslam]

Yes, 0 explanation. My favorite reasons to dislike a video.