Eu estava passando por algumas perguntas da entrevista da Amazon no CareerCup.com e me deparei com essa pergunta interessante que não consegui descobrir como fazer. Estou pensando nisso há 2 dias. Ou estou adotando uma abordagem diferente, ou é uma função genuinamente difícil de escrever.

A pergunta é a seguinte:

Escreva uma função em C que descubra se uma string é uma sub-string de outra. Observe que uma incompatibilidade de um caractere deve ser ignorada.

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’

O valor de retorno não foi mencionado na pergunta, portanto, assumo que a assinatura da função possa ser algo como isto:

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

Se houver uma correspondência com as regras fornecidas, retorne o ponteiro para o início da substring correspondente dentro da string. Outro retorno nulo.

Bônus

Se alguém também puder descobrir uma maneira genérica de tolerar n em vez de 1, isso seria simplesmente brilhante. Nesse caso, a assinatura seria:

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

Obrigado a todos que tentaram isso e compartilharam sua solução bem-sucedida.