After changing the submit button, I would put:

• Populate the search form on the Not Found page with the original search string.