substring search without using built in utils

[John Machin]

Steven D'Aprano wrote:
> On Thu, 09 Nov 2006 03:31:02 -0800, John Machin wrote:
>
> >
> > Bruno Desthuilliers wrote:
> >> Gabriel Genellina wrote:
> >> > At Wednesday 8/11/2006 22:29, zeal elite wrote:
> >> >
> >> >> I am looking for substring search python program without using the
> >> >> built in funtions like find, or 'in'.
> >> >
> >> > The only reasonable usage for such a constraint would be a school
> >> > assignment so: don't cheat and do your homework!
> >> >
> >>
> >> OTHO, looking for existing solutions to a same or similar problem and
> >> studying them is usually considerer good practice in real-life
> >> programming jobs !-)
> >>
> >
> > Looking at an existing solution for substring search that was coded in
> > Python, instead of using the built-in functionality would IMHO be
> > considered extremely bad practice in a real-life programming job.
>
> Sure. But what if the data type in question wasn't a string, but a list?
>
>
> Given a source list, find the offset of a target sub-list within the
> source list, in other words, find for lists.
>
> i.e. search(source, target) returns n if source[n:n+len(target)] == target
> for any sequence type.
>

In that case, in a real-life enterprisey environment, you'd just code
up the brute-force naive method and wait till someone screamed about
the speed. If that happened, you'd have a look at how "find" was
implemented for unicode, because it can't use any tricks that depend on
there being a small number (e.g. 256) of symbols in the alphabet,
and/or you'd fire up your googler and see what had been done outside
Python ...

> Yes, I know I'm changing the constraints of the problem.
(a) There wasn't a problem to start with.
(b) It's called "moving the goalposts".

> Now for a real
> challenge, change the search from a one-dimensional data structure to two.
>
> (The solution is left as an exercise for the class.)

The class knows all about Google. Better leap into the seat of your
plagiarism detection machine and start pedalling :-)