Количество символов, сравниваемых во время сопоставления наивной строки

Question

Меня попросили найти количество символов, которые сравниваются во время сопоставления наивной строки. Эту функцию нам было предложено реализовать:

// Count the number of characters compared while finding all occurences of the pattern in the given text
// Characters must be matched from left to right
int charactersCompared(char *pattern, char *text);

Так что, если текст: «ABCEDF» и шаблон: «EF», то количество символов, которые я бы сравнил, используя грубую силу Метод будет 6 (сравнение первой буквы текста с первой буквой шаблона. Если он не совпадает, сравните вторую букву текста с первой буквой шаблона еще раз. Если он совпадает, продолжите с сравнение следующих букв текста и рисунка и т. д.)

Изучив логи c со многими примерами, я реализовал вышеуказанную функцию следующим образом:

int charactersCompared(char *pattern, char *text)
{
    int i,j,comp=0; 
    int flag;

    for(i=0;text[i]!='\0';i++)    //iterating through all the letters of text
    {
        for(j=0;pattern[j]!='\0';j++)
        {
            comp++;             //to count one comparision. 
            if(text[i+j]==pattern[j])   //to check if similar to pattern
            {
                flag=1;          
                continue;
            }
            else
            {
                if(flag==1)
                {
                    flag=0;
                    comp--;
                }
                break;
            }
        }
    }
    //printf("VALUE OF C=%d\n",comp);
    return comp;
}

Это прекрасно работает для пары (ABCDEF, EF) (где количество равно 6), но не для других тестовых случаев, которые включают в себя несколько вхождений шаблона в тексте, таких как: Text: ABCDEFGHEIEF Pattern: EF

I ' Я должен получить 14 сравнений, в то время как мой вывод 12. Я не понимаю, где я пропускаю.

Если кто-то может указать, что является неисправной логикой c, это будет большой помощи Или, если есть более простой способ сделать это, предложения приветствуются. Единственным ограничением является то, что метод должен быть методом грубой силы (т.е. я не могу реально изменить часть, где я сравниваю каждый символ каждой строки).

Спасибо, что уделили время!

Answer 1

Итак, я выяснил, почему моя программа увеличила количество раз в ответе, опубликованном @END. Это было потому, что внешний для l oop продолжался до тех пор, пока каждая буква в тексте не сравнивалась. Но когда мы делаем это вручную, это происходит только до тех пор, пока количество букв, оставшихся в тексте при сравнении, не станет больше или равно количеству букв в шаблоне. Так что я изменил условие

int charactersCompared(char *pattern, char *text)
{
    int i,j,comp=0; //int flag;
    int lenp=length(pattern),lent=length(text);
    for(i=0;i<=lent-lenp;i++)
    {

        for(j=0;pattern[j]!='\0';j++)
        {
            comp++;
            if(text[i+j]==pattern[j])
            {
                continue;
            }
                break;
        }
    }
    //printf("VALUE OF C=%d\n",c);
    return comp;
}

Это имеет смысл и работает! Спасибо тем, кто пытался ответить!

Answer 2

Обратите внимание, что в худшем случае n(m-n+1), где n - длина шаблона, а m - длина текста. Теперь, поскольку вы хотите вычислять только сравнения, переменная flag не требуется. Предпочитают KISS принцип.

for(i=0;text[i]!='\0';i++)    //iterating through all the letters of text
{
    for(j=0;pattern[j]!='\0';j++)
    {
        comp++;             //to count one comparison. 
        if(text[i+j]==pattern[j])   //to check if similar to pattern
            continue;
        break;
     }
}
printf("VALUE OF C=%d\n",comp);