How about the Google diff-match-patch code? https://github.com/elliotlaster/Ruby-Diff-Match-Patch
I've used it in the past and been happy with the results.
Taken from the documentation linked above:
# Diff-ing
dmp.diff_main("Apples are a fruit.", "Bananas are also fruit.", false)
=> [[-1, "Apple"], [1, "Banana"], [0, "s are a"], [1, "lso"], [0, " fruit."]]
You would just need to iterate through the non-matches and find the character position in the appropriate string.
pos_ary = s.enum_for(:scan, /search_string/).map { regexp.last_match.begin(0) }