Is it possible to replace occurrences of a character sequence recursively without iterating over the same sequence again?

By performing a sed as in the following scenarios I can get the mentioned output.

$ echo XX | sed -e 's/XX/XoX/g'
XoX  
$ echo XXX | sed -e 's/XX/XoX/g'
XoXX  
$ echo XXXX | sed -e 's/XX/XoX/g'
XoXXoX  

However, I'm expecting the output to follow the following behavior.

Input:

XX
XXX
XXXX

Expected output:

XoX
XoXoX
XoXoXoX

Is it possible to achieve the expected behavior with sed alone?

up vote 23 down vote accepted

You can do:

> echo XXXX | sed -e ':loop' -e 's/XX/XoX/g' -e 't loop'
XoXoXoX

With:

  • -e ':loop' : Create a "loop" label
  • -e 't loop' : Jump to the "loop" label if previous substitution was successful

In this particular case look-ahead or look-behind would be useful. I think GNU sed doesn't support these. With perl:

perl -ne 's/X(?=X)/Xo/g; print;'

You could also use lookbehind and lookahead like:

s/(?<=X)(?=X)/o/g

Where:

(?<=X) is a positive lookbehind, a zero-length assertion that make sure we have an X before the current position
(?=X) is a positive lookahead, a zero-length assertion that make sure we have an X after the current position

Using in a perl one-liner:

perl -pe 's/(?<=X)(?=X)/o/g' inputfile

Where:

-p causes Perl to assume a loop around the program with an implicit print of the current line

The looping answer is the general way to do what you are asking.

However in the case of your data, assuming you are using GNU you can simply do:

sed 's/\B/o/g'

The \b and \B options are regex extensions:

  • \b matches word boundaries, i.e. the transition from a "word" character to "non-word" character, or vice-versa
  • \B matches the opposite of \b. i.e. the gaps "inside" words. This allows us to insert characters inside of a word but not outside, as required.

Try it online.

This assumes that the input characters are in fact all "word" characters.


Alternatively if you don't have GNU sed, or if the input characters are not all "word" characters, you can still achieve your goal without looping:

sed 's/./&o/g;s/o$//'

This simply places an o after every character and then removes the final o from the string.

Try it online.

  • 1
    This assumes that input strings consist of some number of X and nothing else. Both solutions fail if there are other characters present... – AnoE Oct 16 at 10:50
  • @AnoE In the second sample, that is fixed with a simple replacement of X by .. Please see edit. – Digital Trauma Oct 16 at 19:09
  • Not equivalent to the case the OP gave. He gave the exact REs he needs (change occurrences of XX in a string). Your versions only give the same result as his for the exact same input strings he gave; not for generic input strings. – AnoE Oct 16 at 20:18

I checked if there is any sort of a flag to make this happen.
Even if that behavior was there it is going to be highly resource consuming.

However, in this particular use case, it is possible to have the expression just twice and achieve the required functionality. i.e. with 2 repeating sed expressions.

echo XX | sed -e 's/XX/XoX/g' -e 's/XX/XoX/g'     # outputs XoX
echo XXX | sed -e 's/XX/XoX/g' -e 's/XX/XoX/g'    # outputs XoXoX
echo XXXX | sed -e 's/XX/XoX/g' -e 's/XX/XoX/g'   # outputs XoXoXoX

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.