Replacing words in a sentence?

I'm trying to replace multiple words with their "pirate pair", for example:

Normal: "Hello sir, where is the hotel?"

Pirate: "Ahoy matey, whar be th' fleagbag inn?"

This is what I tried before:

#include<iostream>
#include<string>
#include<conio.h>

using namespace std;

void speakPirate(string s);

int main()
{
    string phrase;

    cout << "Enter the phrase to Pirate-Ize: ";
    getline(cin, phrase);

    speakPirate(phrase);

    _getch();
    return 0;
}

void speakPirate(string s)
{
    int found;

    // list of pirate words
    string pirate[12] = { "ahoy", "matey", "proud beauty", "foul blaggart", "scurvy dog", "whar", "be", "th'", "me", "yer", "galley", "fleabag inn" };

    // list of normal words
    string normal[12] = { "hello", "sir", "madam", "officer", "stranger", "where", "is", "the", "my", "your", "restaurant", "hotel" };

    for (int i = 0; i < s.length(); i++)
    {
        found = s.find(normal[i]);

        if (found > -1)
        {
            string left = s.substr(0, found - 1);   // get left of the string
            string right = s.substr(found + pirate[i].length(), s.length());  // get right of string
            s = left + " " + pirate[i] + " " + right;   // add pirate word in place of normal word
        }
    }

    cout << s;
}

But it didn't really work and was very buggy, so I tried using the replace() function instead:

#include<iostream>
#include<string>
#include<conio.h>

using namespace std;

void speakPirate(string s);

int main()
{
    string phrase;

    cout << "Enter the phrase to Pirate-Ize: ";
    getline(cin, phrase);

    speakPirate(phrase);

    _getch();
    return 0;
}

void speakPirate(string s)
{
    int found;

    // list of pirate words
    string pirate[12] = { "ahoy", "matey", "proud beauty", "foul blaggart", "scurvy dog", "whar", "be", "th'", "me", "yer", "galley", "fleabag inn" };

    // list of normal words
    string normal[12] = { "hello", "sir", "madam", "officer", "stranger", "where", "is", "the", "my", "your", "restaurant", "hotel" };

    for (int i = 0; i < s.length(); i++)
    {
        found = s.find(normal[i]);

        if (found > -1)
        {
            s.replace(found, found + pirate[i].length(), pirate[i]);
        }
    }

    cout << s;
}

I'm not sure why, but this doesn't really work either. I also notice that when I try changing a larger word into a smaller word, some of the original word is leftover, for example:

    Enter the phrase to Pirate-Ize: hello
    ahoyo

And I just noticed that it sometimes might not even change the word at all, for example:

    Enter the phrase to Pirate-Ize: where
    where

How come? Could someone please tell me what I need to do or a more effective solution that I could implement? Thanks a lot.