проверка строка является подстрокой другой строки

Question

Как проверить, является ли строка подстрокой другой строки в C, не используя функцию substr?

Answer 1

Вы можете использовать метод скользящего хэша ( Рабин-Карп ) или реализовать KMP , который немного похож на конечный автомат.

Как правило, Рабин-Karp используется при поиске нескольких целевых строк, потому что вторая проверка, которая требуется (для фактического равенства, а не просто хеш-равенства), стоит того, чтобы иметь возможность проверить исходную строку только один раз.В вашем случае с любым из них все будет в порядке.

Существует также более наивное решение, которое O (n ^ 2) и требует проверки целевой строки в каждой позиции исходной строки.

Answer 2

Не используйте substr… используйте strstr / strnstr!

Серьезно, ничто иное не будет таким быстрым, если только оно не сделает точно то же самое. Почему ты не хочешь этого?

Редактировать: да, есть алгоритмы с лучшей асимптотикой. Для текстовых поисков по одной строке я был бы очень удивлен, увидев, что что-то превосходит стандартную библиотеку.

Answer 3

void main()
{
    char str[80],search[10];
    int count1=0,count2=0,i,j,flag;




    puts("Enter a string:");
    gets(str);

    puts("Enter search substring:");
    gets(search);

    //determines the src length
    while (str[count1]!='\0')
        count1++;
    //determines the key length
    while (search[count2]!='\0')
        count2++;

    for(i=0;i<=count1-count2;i++)
    {
        for(j=i;j<i+count2;j++)
        {
            flag=1;
            if (str[j]!=search[j-i])
            {
                flag=0;
               break;
            }
        }
        if (flag==1)
            break;
    }
    if (flag==1)
        puts("SEARCH SUCCESSFUL!");
    else
        puts("SEARCH UNSUCCESSFUL!");
    getch();
}