[Tutor] Best way to alter sections of a string which match dictionary keys?

[SSokolow]

I have a proxy which stores a list of URLs visited withing a certain 
server as keys in a dictionary and currently all the values are just set 
to 1 (I have some ideas for future expansion though.) Originally this 
was just because it was the easiest way to prevent duplication of entries.

Example: {'/2048.html': 1, '/index.html': 1, '/1.html': 1}

My problem is that I want to add <img src="_proxy/checkmark.png" /> 
beside every hyperlinked block of text which links to one of these URLs. 
A while ago when I made the Perl CGI version (aborted), the only way I 
could find was to waste resources using this code:

while( ($key, $value)=each %viewedEpisodes) {
  $file=~s/(.*)<a(.*)href="($key)"(.*)>(.*)/$1<img 
src="$imgDir\/check.png"><a$2href="$3"$4>$5/ig;
}

which is roughly equivalent to: (I didn't have time to test this)

for URL in viewedEpisodes|.keys()
    file = re.sub(r'||(?i)||(<a.*?href="' + URL + r'".*?)', file, 
||r'<img src="' + imgDir + r'/check.png">\1')


|I could just use that code in Python (It would work, right?) but it 
would be a complete waste of processor cycles.
What would be the best way to accomplish the task without wasting so 
much time looping?

Thanks

Stephan Sokolow