Google interview questions: print matching chars in order of first string

// http://www.impactinterview.com/2009/10/140-google-interview-questions/#software_engineer
// Write a function f(a, b) which takes two character string arguments and returns a string containing
// only the characters found in both strings in the order of a. Write a version which is order N-squared
// and one which is order N.

#include <iostream>
#include <string>
#include <functional>
#include <vector>
#include <cstring>

std::string match_the_stupid_way(std::string a, std::string b)
{
    // the silly way is just for each char in string a O(n)
    // look through string b O(n) double loop hence O(n^2)

    std::string res;

    for (std::string::iterator ait = a.begin();
         ait != a.end();
         ++ait)
    {
        // ok match the first each char
        std::string::iterator bit = b.begin();
        while (bit != b.end() and
               *bit != *ait)
        {
            ++bit;
        }

        if (bit != b.end())
            res += *ait;
    }
    return res;
}

std::string match_the_fast_way(std::string a, std::string b)
{
    // O(N) .. this imples reading over a string (which takes O(N)) and
    // digesting into an O(1) data struture and then check over the other...

    // well an O(1) data structure is a hash or table..
    std::vector<bool> found_char(256,false);

    // the O(N) read is
    for (std::string::iterator bit = b.begin();
         bit != b.end();
         ++bit)
    {
        found_char[*bit] = true;
    }

    // and the second O(N) check is
    std::string res;
    for (std::string::iterator ait = a.begin();
         ait != a.end();
         ++ait)
    {
        if (found_char[*ait])
            res += *ait;
    }

    return res;
}

void test(std::function<std::string (std::string,std::string)> func,
          std::string a,
          std::string b,
          std::string exp)
{
    std::string out = func(a,b);

    std::cout << (out == exp ? "passed" : "FAILED")
              << " a:\""     << a
              << "\" b:\""   << b
              << "\" out:\"" << out
              << "\" exp:\"" << exp
              << "\"\n";
}

void test_set(std::function<std::string (std::string,std::string)> func)
{
    test(func, "a", "cba", "a");
    test(func, "aaa", "cba", "aaa");  // hmm question isnt clear on repeats.. assume it does repeats
    test(func, "abcdefg", "gfedcba", "abcdefg");
    test(func, "the quick brown fox", "peter piper picked a pepper", "te ick r ");
    std::cout << "*** SET DONE ***\n";
}

int main()
{
    test_set(match_the_stupid_way);
    test_set(match_the_fast_way);
}

Output is

passed a:"a" b:"cba" out:"a" exp:"a"
passed a:"aaa" b:"cba" out:"aaa" exp:"aaa"
passed a:"abcdefg" b:"gfedcba" out:"abcdefg" exp:"abcdefg"
passed a:"the quick brown fox" b:"peter piper picked a pepper" out:"te ick r " exp:"te ick r "
*** SET DONE ***
passed a:"a" b:"cba" out:"a" exp:"a"
passed a:"aaa" b:"cba" out:"aaa" exp:"aaa"
passed a:"abcdefg" b:"gfedcba" out:"abcdefg" exp:"abcdefg"
passed a:"the quick brown fox" b:"peter piper picked a pepper" out:"te ick r " exp:"te ick r "
*** SET DONE ***