Подстрока соответствия в строке с допуском 1 символьного несоответствия

Я проходил некоторые вопросы об интервью Amazon на CareerCup.com, и я столкнулся с этим интересным вопросом, который я не смог выяснить, как сделать. Я думал на этом с 2 дней. Или я беру путь от подхода, или это - по-настоящему трудная функция для записи.

Вопрос следующие:

Запишите функцию в C, который может найти, является ли строка подстрокой другого. Обратите внимание, что несоответствие одного символа должно быть проигнорировано.

A mismatch can be an extra character: ’dog’ matches ‘xxxdoogyyyy’  
A mismatch can be a missing character: ’dog’ matches ‘xxxdgyyyy’ 
A mismatch can be a different character: ’dog’ matches ‘xxxdigyyyy’

Возвращаемое значение не было упомянуто в вопросе, таким образом, я предполагаю, что подпись функции может быть чем-то вроде этого:

char * MatchWithTolerance(const char * str, const char * substr);

Если существует соответствие с данными правилами, возвратите указатель на начало подобранной подстроки в строке. Еще возвратите пустой указатель.

Премия

Если бы кто-то может также выяснить универсальный способ сделать допуск к n вместо 1, то это было бы просто блестящим. В этом случае подпись была бы:

char * MatchWithTolerance(const char * str, const char * substr, unsigned int tolerance = 1);

Благодаря всем те, кто делал бы попытку этого и совместно использовал бы их успешное решение.