Ну что замучились искать алгоритмы поиска подстроки? Привожу метод, который РАБОТАЕТ! Сам пробовал :-)
int find_substring(char s[], char q[]){
int i, j, N, M;
N = strlen(s);
M = strlen(q);
int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М*/
/* Вычисление префикс-функции */
i=0;
j=-1;
d[0]=-1;
while(i=0) && (q[j]!=q[i]))
j = d[j];
i++;
j++;
if(q[i]==q[j])
d[i]=d[j];
else
d[i]= j;
}
/* поиск */
for(i=0,j=0;(i=0)&&(q[j]!=s[i]))
j=d[j];
free (d); /* освобождение памяти массива d */
if (j==M)
return i-j;
else /* i==N */
return -1;
}