# Subsequence regular expression

**URL:** <https://www.ruby-forum.com/t/subsequence-regular-expression/97090>\
**Category:** Ruby\
**Created:** [January 25, 2006, 7:10am UTC](https://www.ruby-forum.com/t/subsequence-regular-expression/97090 "2006-01-25T07:10:13Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![diz\_rael](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c67d28/32.png) [@diz\_rael](https://www.ruby-forum.com/u/diz_rael)\
**Post date:** [January 25, 2006, 7:10am UTC](https://www.ruby-forum.com/t/subsequence-regular-expression/97090/1 "2006-01-25T07:10:13Z")

</div>

Hi,

I’m trying to extract a certain sequence from a  
string. Best described by example:

s =  
“5b300ba00260bababababababababababababababababa000bd1007bd10b810ba92”  
slice^--------------------------------------------^

I want to extract a slice of the string starting from  
the beginning and extending upto the end of the long  
“ba” sequence. What I’m trying to do is post-process a  
large dump of memory from an embedded system. The  
stack region is initially cleared out to bababa… So  
after the application finishes, the “dirty” portion  
gives the depth of the stack. There may be stray “ba”  
values at various places in memory written during the  
normal course of the application’s execution. In the  
above  
example, the “dirty” portion is  
5b300ba00260.

Anyway, I tried the following:

s=~/.+?(ba)+/  
$& =\> “5b300ba”

It so happens that a “ba” was created on the stack, so  
the regexp thinks it ends there, when in fact the  
string I want it to return is:  
5b300ba00260

Is there a regexp that can handle this or is this a  
fundamentally difficult algorithmic problem (kind of  
related to longest common subsequence I guess).

Any help will be appreciated. Thanks a lot!

---

<div class="post-metadata">

**Author:** ![diz\_rael](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c67d28/32.png) [@diz\_rael](https://www.ruby-forum.com/u/diz_rael)\
**Post date:** [January 25, 2006, 8:13am UTC](https://www.ruby-forum.com/t/subsequence-regular-expression/97090/2 "2006-01-25T08:13:39Z")

</div>

On Wed, 25 Jan 2006 15:07:31 +0900, diz rael [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:  
[snip]

> Anyway, I tried the following:
> 
> s=3D~/.+?(ba)+/  
> $& =3D\> “5b300ba”
> 
> It so happens that a “ba” was created on the stack, so  
> the regexp thinks it ends there, when in fact the  
> string I want it to return is:  
> 5b300ba00260

Well, you could just check for 2 or more ‘ba’ sequences:

s =~ /(.\*?)(ba){2,}/  
p $1

but of course, your “dirty portion” just might just have two, or even  
more,  
stray ‘ba’ in a row – so I suspect you want to grab everything from the  
beginning up to the longest subsequence of repeated 'ba’s? One way:

s = “5bbaba300ba00260babababababababababababa000bd1007b810ba92”  
puts s[0,s.index(s.scan(/(?:ba)+/).max)]

But I may well be missing an easier way 🙂

cheers,  
andrew

---

<div class="post-metadata">

**Author:** ![diz\_rael](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c67d28/32.png) [@diz\_rael](https://www.ruby-forum.com/u/diz_rael)\
**Post date:** [January 25, 2006, 8:31am UTC](https://www.ruby-forum.com/t/subsequence-regular-expression/97090/3 "2006-01-25T08:31:45Z")

</div>

On 1/25/06, diz rael [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:  
[snip]

> In the above example, the “dirty” portion is  
> 5b300ba00260.

s =  
“5b300ba00260bababababababababababababababababa000bd1007bd10b810ba92”  
p s.scan(/(?:ba){2,}|(?:[^b][^a])+/)  
#[“5b300ba00260”, “bababababababababababababababababa”,  
“000bd1007bd10b810ba9”]

---

<div class="post-metadata">

**Author:** ![diz\_rael](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c67d28/32.png) [@diz\_rael](https://www.ruby-forum.com/u/diz_rael)\
**Post date:** [January 25, 2006, 11:17am UTC](https://www.ruby-forum.com/t/subsequence-regular-expression/97090/4 "2006-01-25T11:17:58Z")

</div>

On 1/25/06, diz rael [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:  
[snip]

> “000bd1007bd10b810ba92”  
> Hmm… the many ba’s is at an odd offset… don’t you want them only at  
> equal offsets?

Maybe like this?

s =  
“5b3000ba00260bababababababababababababababababa000bd1007bd10b810ba92”  
p s.scan(/\G(?: (?:ba)+ | (?:(?!ba)…)+ )/x)

# [“5b3000”, “ba”,

“00260bababababababababababababababababa000bd1007bd10b810”, “ba”,  
“92”]

---

<div class="post-metadata">

**Author:** ![diz\_rael](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/c67d28/32.png) [@diz\_rael](https://www.ruby-forum.com/u/diz_rael)\
**Post date:** [January 25, 2006, 10:44am UTC](https://www.ruby-forum.com/t/subsequence-regular-expression/97090/5 "2006-01-25T10:44:48Z")

</div>

Thanks a lot for the suggestions. This is close to  
what I’m looking for, but I don’t quite get the effect  
of “?:”

The docs say that it simply makes the regexp into a  
group without generating backreferences. Doesn’t this  
mean that _not_ using ?: will only have the  
side-effect of setting $1, $2, etc.

However,:  
p s.scan(/(ba){2,}|([^b][^a])+/)  
=\> [[nil, “60”], [“ba”, nil], [nil, “a9”]]

Another thing is that in the sample string in my  
original post, the first “ba” happens to occur on an  
odd location (string indexed from 0). If I shift it  
forward by a character it doesn’t work as well:

s =  
“5b3000ba00260bababababababababababababababababa000bd1007bd10b810ba92”  
p s.scan(/(?:ba){2,}|(?:[^b][^a])+/)  
=\> [“5b3000”, “a00260”,  
“bababababababababababababababababa”,  
“000bd1007bd10b810ba9”]

ideally, it should be:  
=\> “5b3000ba00260”  
“bababababababababababababababababa”  
“000bd1007bd10b810ba92”

Thanks in advance…

— Simon S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> s =

“5b300ba00260bababababababababababababababababa000bd1007bd10b810ba92”