Search and delete substrings from a string

Question

I want to remove all instances of a string(smaller or equal) than another string. Even overlapping substrings should be completely removed. This is the code I have written:

#include<stdio.h>

int Checknremove(char *str,char *ph)
{
        while( *str )
        {
                char *k=ph,*s=str;
                while( *k && *k==*s ) ++k,++s;
                if( !*k )
                {
                        while( *s ) *str++=*s++;
                        *str=0;
                        return 1;
                }
                ++str;
        }
        return 0;
}

int main()
{
        int t;
        scanf("%d", &t);
        while(t--)
        {
                char str[100], ph[100];
                scanf("%s %s", str, ph);
                while(Checknremove(str,ph));
                puts(str);
        }
        return 0;
}

The problem is it only removes the substrings which are distinct and not overlapping ones. Example: catafjkgjcat cat will output afjkgj but aababbaababbac aababba will output ababbac and not c as I want it to. What should I do?

Answer 1

The problem of course is the "nremove". If you do the remove AS you scan (i.e. immediately), the overlapping part will no longer be in the str to match on the next iteration/call.

What you should do is separate the checking from the removing: do all the checking before doing ANY removing. You'll have to store string indexes or something to communicate between the two.

Answer 2

aababbaababbac has two aababba, but they are overlapped.

You should mark where to delete first, and then remove marked characters instead of deleting what you found immediately.

UPDATE: here is a sample implementation.

#include<stdio.h>
#include<stdlib.h> /* for using malloc */
#include<string.h> /* for using strlen and strncmp */

/* add const since it won't be modified */
/* made the return value void since this will remove all target by one call */
void Checknremove(char *str,const char *ph)
{
        size_t srclen = strlen(str);
        size_t targetlen = strlen(ph);
        char *delete_flag = calloc(srclen, 1);
        size_t i, j;
        if(delete_flag == NULL) exit(1); /* failed to allocate the memory */
        /* search the target and mark it */
        for(i = 0; i <= srclen - targetlen; i++)
        {
                if(strncmp(str + i, ph, targetlen) == 0)
                {
                    for (j = 0; j < targetlen; j++) delete_flag[i + j] = 1;
                }
        }
        /* copy undeleted characters to str */
        for (i = j = 0; i < srclen; i++)
        {
                if (!delete_flag[i]) str[j++] = str[i];
        }
        str[j] = '\0';
        free(delete_flag);
}

int main()
{
        int t;
        scanf("%d", &t);
        while(t--)
        {
                char str[100], ph[100];
                scanf("%s %s", str, ph);
                Checknremove(str,ph);
                puts(str);
        }
        return 0;
}