As a variant to index, perhaps using pos would work, and then you could offset the find by the length of the thing you're looking for.

#!/usr/bin/perl

use strict;
use warnings;

while (<DATA>) {
    my $search = 'foo';
    if (/foo/g) {
        print "Line $. Col ",
              pos() - length($search),
              ": $search found.\n";
    }
}

__DATA__
This is a test.
This is foo.
foo is good.

# Results
#Line 2 Col 8: foo found.
#Line 3 Col 0: foo found.
[download]

Hope this helped,
-v.