#include <iostream>
#include <string>
#include <cstring>
 
using std::cin;
using std::cout;
using std::endl;
using std::string;
 
const char* Find(const char *szOrig, const char *szSearch)
{
    const char *szResult = szOrig;
    while (*szResult && strlen(szResult) >= strlen(szSearch))
    {
        int r = strncmp(szResult, szSearch, std::min(strlen(szSearch), strlen(szResult)));
        //cout << r << " - " << int(szResult - szOrig) << endl;
        if (!r) break;
        szResult++;
    }
    return *szResult ? (strlen(szResult) >= strlen(szSearch) ? szResult : NULL) : NULL;
}
 
char* Replace(const char *szOrig, const char *szSearch, const char *szReplace)
{
    unsigned int maxMatches = strlen(szOrig) / strlen(szSearch);
    const char **arrMatches = new const char*[maxMatches];
    unsigned int matches = 0;
    const char *szResult = szOrig;
    while (szResult)
    {
        szResult = Find(szResult, szSearch);
        if (szResult)
        {
            arrMatches[matches++] = szResult;
            szResult += strlen(szSearch);
        }
    }
    char *szNew = NULL;
    if (matches)
    {
        cout << "Matches: " << matches << endl;
        //Calculate the new string size.
        unsigned int newSize = strlen(szOrig) + matches * (strlen(szReplace) - strlen(szSearch)) + 1;
        cout << "New size: " << newSize << endl;
        szNew = new char[newSize];
        //memset(szNew, 0, newSize);
        char *szCurPos = szNew;
        //Concatenate
        const char *szStart = szOrig;
        for(unsigned int i = 0; i < matches; i++)
        {
            strncpy(szCurPos, szStart, arrMatches[i] - szStart);
            szCurPos += arrMatches[i] - szStart;
            strncpy(szCurPos, szReplace, strlen(szReplace));
            szCurPos += strlen(szReplace);
            szStart = arrMatches[i] + strlen(szSearch);
        }
        //Copy any remainder and null-terminate the string.
        if (szStart < szOrig + strlen(szOrig))
        {
            strncpy(szCurPos, szStart, strlen(szStart));
        }
        szNew[newSize - 1] = '\0';
    }
    delete[] arrMatches;
    return szNew;
}
 
int main()
{
    string strSentence;
    string strSearch;
    string strReplace;
    getline(cin, strSentence);
    getline(cin, strSearch);
    getline(cin, strReplace);
    cout << "Sentence:  " << strSentence << " - " << strSentence.size() << " characters." << endl;
    cout << "Search string:  " << strSearch << " - " << strSearch.size() << " characters." << endl;
    cout << "Replace string:  " << strReplace << " - " << strReplace.size() << " characters." << endl;
    //const char *szResult = Find(strSentence.c_str(), strSearch.c_str());
    //cout << (szResult ? szResult : "No matches found.") << endl;
    char *szNewString = Replace(strSentence.c_str(), strSearch.c_str(), strReplace.c_str());
    if (szNewString)
    {
        cout << "New String (" << strlen(szNewString) << " chars):  " << endl << szNewString << endl;
        delete[] szNewString;
    }
    return 0;
}