a RegEx puzzle

Roy Smith roy at panix.com
Fri Mar 11 15:24:01 CET 2005


Charles Hartman <charles.hartman at conncoll.edu> wrote:
> I'm still shaky on some of sre's syntax. Here's the task: I've got 
> strings (never longer than about a dozen characters) that are 
> guaranteed to be made only of characters 'x' and '/'.

One possibility is to cheat completely, and depending on memory constraints 
and how often you need to do this, it might even make sense to do so.

There's only two possible values for each character, so you're really 
dealing with binary numbers.  The max length is 12 characters (I'm 
deliberately being oblivious to where you said "about" :-)), so there are 
only 2^12 or 4096 possible strings.  You could probably afford to 
pre-compute all 4096 strings, use them as dictionary keys, and store a 
(start, end) tuple for each key.  Computation then becomes a simple 
dictionary lookup.

> In each string I 
> want to find the longest continuous stretch of pairs whose first 
> character is 'x' and the second is either mark. So if marks = 
> '/xx/xxx///', the "winning" stretch begins at position 2 and is 6 
> characters long ('x/xxx/'), which requires finding a second match that 
> overlaps the first match (which is just 'xx' in position 1). (When 
> there are multiple "winning" stretches, I might want to adjudicate 
> among them, but that's a separate problem.) I hope this is clear 
> enough.

Unfortunately, no, it's not very clear.  In fact, I have no clue what 
you're trying to do.  Could you try explaining it again?

> Charles Hartman
> Professor of English, Poet in Residence

Hmmm.  Are you, by any chance, looking for meter patterns in verse?



More information about the Python-list mailing list