Estaba revisando algunas preguntas de la entrevista de Amazon en CareerCup.com, y me encontré con una pregunta interesante que no he podido averiguar cómo hacer. He estado pensando en esto desde hace 2 días. O me estoy alejando, o es una función realmente difícil de escribir.

La pregunta es la siguiente:

Escriba una función en C que pueda encontrar si una cadena es una subcadena de otra. Tenga en cuenta que se debe ignorar la falta de coincidencia de un carácter.

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’

El valor de retorno no se mencionó en la pregunta, por lo que supongo que la firma de la función puede ser algo como esto:

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

Si hay una coincidencia con las reglas dadas, devuelva el puntero al comienzo de la subcadena coincidente dentro de la cadena. De lo contrario, volver nulo.

Prima

Si alguien también puede encontrar una forma genérica de hacer la tolerancia a n en lugar de 1, entonces eso sería genial. En ese caso la firma sería:

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

Gracias a todos los que intentaron esto y compartieron su solución exitosa.