Do it from back to front.

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1200077

use strict;
use warnings;

my $string = 'Titles consisting of a single word are discouraged, and 
+in most cases are disallowed outright.';

my @tags = split /\n/, <<END;
consisting of: cat1: id1: 7: 20
discouraged: cat1: id2: 39: 50
most cases: cat2: id3: 59: 69
END

print "$string\n";

for (reverse @tags)
  {
  my ($text, $cat, $id, $start, $end) = split /: /;
  substr $string, $start, $end - $start, "($cat: $id)$text($cat)";
  }

print "$string\n";
[download]

Outputs:

Titles consisting of a single word are discouraged, and in most cases 
+are disallowed outright.
Titles (cat1: id1)consisting of(cat1) a single word are (cat1: id2)dis
+couraged(cat1), and in (cat2: id3)most cases(cat2) are disallowed out
+right.
[download]