c - 简单字符串匹配期间比较的字符数

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(将文本的第一个字母与模式的第一个字母。如果不匹配，则再次将文本的第二个字母与模式的第一个字母进行比较。 如果匹配，则继续比较文本和模式的下一个字母等)

在通过很多例子弄清楚逻辑后，我这样实现了上面的功能:

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)效果很好，但对于其他包含文本中多次出现该模式的测试用例则不起作用，例如: 文本:ABCDEFGHEIEF 图案:EF

我应该得到 14 次比较，而我的输出是 12 次。我不明白我错过了什么。

如果有人能指出什么是错误的逻辑，那将会有很大的帮助。或者如果有更简单的方法来做到这一点，建议表示赞赏。唯一的限制是该方法必须是暴力方法(即我无法真正更改比较每个字符串的每个字符的部分)。

感谢您的宝贵时间!

Answer 1

请注意，最坏​​的情况是 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);