To nie takie proste, bo jeżeli pomiędzy '<a' a 'href' zezwoli na dowolny znak, to wtedy takie co¶:
<a href="podstrona">aaaa</a> fsdjfkdajf <a href="index">bbbbb</a>
zostanie wykryte jako jeden link, trzeba to bardziej ograniczyć, prędzej co¶ takiego:
<?php
$string = ' dsaf sdaf saf as fas<a class="normal_link" href="index.php/podstrona/1" title="tttasa">aa</a> fdsa fsad fsa <a href="index.php">hh</a> fsdf sfsda fsa fa s<a href="podstrona.html" class="super_class" title="tytuł">yyyy</a> <a href="podstrona.html" class="super_class" title="tytuł">yyyy</a> <a href="podstrona.html" class="super_class" title="tytuł">yyyy</a>';
$string2 = preg_replace('/<a([A-za-z0-9=\'\" ˇ±ĘęĆ榶ÓóŁłŃń]*)href="([A-za-z0-9.\/]*)"([A-za-z0-9=\'\" ˇ±ĘęĆ榶ÓóŁłŃń]*)>([A-za-z0-9]*)<\/a>/i', '<a$1href="$2"$3 rel="no follow">$4</a>', $string); ?>
ale i ten przykład może nie działać do wszystkich linków, musisz z tym trochę pokombinować i pomy¶leć nad wszystkimi znakami jakie mog± być dostępne, albo wykluczyć żeby znaki pomiędzy '<a', 'href' itd nie mogły być zamknięciami i otwarciami tagów html, < , >
//EDIT
to będzie lepsze:
<?php
$string = ' dsaf sdaf saf as fas<a class="normal_link" href="index.php/podstrona/1" title="tttasa">aa</a> fdsa fsad fsa <a href="index.php">hh</a> fsdf sfsda fsa fa s<a href="podstrona.html" class="super_class" title="tytuł">yyyy</a> <a href="podstrona.html" class="super_class" title="tytuł">yyyy</a> <a href="podstrona.html" class="super_class" title="tytuł">yyyy</a>';
$string2 = preg_replace('/<a([^<>]*)href="([^<>]*)"([^<>]*)>([^<>]*)<\/a>/i', '<a$1href="$2"$3 rel="no follow">$4</a>', $string); ?>
z wykluczeniem < i > wewn±trz, co nie pozwoli żeby 2 linki były rozpoznane jako jeden