#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iterator>
#include <cstring>
using namespace std;

template <class ReturnContainer, typename InIterator>
ReturnContainer find_and_replace_all_copy(
    const InIterator haystack_begin, 
    const InIterator haystack_end, 
    const InIterator needle_begin, 
    const InIterator needle_end, 
    const InIterator replacement_begin, 
    const InIterator replacement_end) {
    
    const typename iterator_traits<InIterator>::difference_type 
    needle_size = distance(needle_begin, needle_end);
    
    const typename iterator_traits<InIterator>::difference_type 
    haystack_size = distance(haystack_begin, haystack_end);
    
    if (haystack_size < 1 || needle_size < 1 || needle_size > haystack_size) {
        return ReturnContainer(haystack_begin, haystack_end);
    }
    
    ReturnContainer result;
    for (InIterator substart = haystack_begin, subend; ; ) {
        subend = search(substart, haystack_end, needle_begin, needle_end);
        copy(substart, subend, back_inserter(result));
        if (subend == haystack_end) {
            break;
        }
        copy(replacement_begin, replacement_end, back_inserter(result));
        substart = subend;
        advance(substart, needle_size);
    }
    return result;
}

template <class ReturnContainer>
ReturnContainer find_and_replace_all_copy(
    const char* haystack, 
    const char* needle, 
    const char* replacement) {
    
    const ReturnContainer haystack_temp(haystack, haystack + strlen(haystack));
    const ReturnContainer needle_temp(needle, needle + strlen(needle));
    const ReturnContainer replacement_temp(replacement, replacement + strlen(replacement));
    
    return find_and_replace_all_copy<ReturnContainer>(
        haystack_temp.begin(), 
        haystack_temp.end(), 
        needle_temp.begin(), 
        needle_temp.end(), 
        replacement_temp.begin(), 
        replacement_temp.end()
    );
}

template <class ReturnContainer, typename InContainer>
ReturnContainer find_and_replace_all_copy(
    const InContainer& haystack, 
    const InContainer& needle, 
    const InContainer& replacement) {
    
    return find_and_replace_all_copy<ReturnContainer>(
        haystack.begin(), 
        haystack.end(), 
        needle.begin(), 
        needle.end(), 
        replacement.begin(), 
        replacement.end()
    );
}

template <class Container>
void printResult(const Container& data) {
    copy(data.begin(), data.end(), ostream_iterator<typename Container::value_type>(cout, ""));
    cout << "\n";
}

int main() {
    typedef vector<char> vuc;
    const string s1("zipmeowbam");
    const string s2("meow");
    const string s3("zam");    
    printResult(find_and_replace_all_copy<string>("zipmeowbam", "meow", "zam"));
    printResult(find_and_replace_all_copy<vuc>("zipmeowbam", "meow", "zam"));
    printResult(find_and_replace_all_copy<vuc>(s1, s2, s3));
    printResult(find_and_replace_all_copy<string>(s1, s2, s3));
    printResult(find_and_replace_all_copy<vuc>(s1.begin(), s1.end(), s2.begin(), s2.end(), 
    s3.begin(), s3.end()));
    printResult(find_and_replace_all_copy<vuc>(s1.rbegin(), s1.rend(), s2.rbegin(), s2.rend(), 
    s3.rbegin(), s3.rend()));
    printResult(find_and_replace_all_copy<string>(s1.rbegin(), s1.rend(), s2.rbegin(), s2.rend(), 
    s3.rbegin(), s3.rend()));
}