String regex match replace for role ‘contributor’ only

There’s author_can() for that:

add_action( 'loop_start', 'wpse105294_nofollow_author' );
function wpse105294_nofollow_author()
{
    ! author_can( $GLOBALS['post']->ID, 'edit_others_posts' )
        AND add_filter( 'the_content', 'cn_nf_url_parse');
}

So you only add that filter callback for authors and other roles that don’t have the possibility to edit_others_posts. By default this is Subscriber and Author. For more info, take a look at the Codex article about Roles and Capabilities.

Edit

As I’ve lately done some stuff with the PHP HTML DOM Parser, I thought it might be better to use this one. For the easiness off things the code was mostly taken from @Alex answer on SO.

add_filter( 'the_content', 'cn_nf_url_parse');
function wpse_105294_Content_Parser( $content )
{
    $dom = new DOMDocument;
    $dom->loadHTML( $content );

    // DOMXPath() might be just too much
    $anchors = $dom->getElementByTagName( 'a' );

    foreach ( $anchors as $a )
    {
        if ( 
            ! $a->hasAttribute( 'rel' )
            OR '' === ( $rel = trim( $a->getAttribute( 'rel' ) ) )
        )
            continue;

        $rel = preg_split( '/\s+/', $rel );

        if ( in_array( 'nofollow', $rel ) )
           continue;

        $rel[] = 'nofollow';
        $anchor->setAttribute( 'rel', implode( ' ', $rel ) );
    }

    $html="";

    // Remove `html\body` before returning
    foreach ( $dom->getElementsByTagName( 'body' )->item(0)->childNodes as $el )
        $html .= $dom->saveXML( $el, LIBXML_NOEMPTYTAG );

    return $html;
}