Locate 2-word U.S. states within string in R

This is not quite the exotic answer but with simple use of str_replace_all we get the desired output:

str_replace_all(search_string, c("(?<=\\n)(\\w+) (?=\\w+)"="\\1_"))

basically the state names are always preceded by a newline (?<=\\n), capture the first word (\\w+) then match a space then check if it’s followed by another word (?=\\w+), only then replace (\\w+) with the captured group plus an underline \\1_