字符串比较的代码优化

Question

我有一个字符串比较的函数代码如下:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int max=0;

int calcMis(char *string,int i, int j,int len)
{
     int mis=0;
     int k=0;
     while(k<len)
     {
             if(string[i+k]!=string[j+k])
                mis+=1;
             if((mis+len-k-1)<=max)
                 return 1;
             else if(mis>max)
                 return 0;
             k=k+1;
     }
}

int main()
{
    char *input=malloc(2000*sizeof(char));
    scanf("%d",&max);
    scanf("%s",input);
    int c=0,i,j,k,x,mis=0;
    int len=strlen(input);
    i=0;
    while(i<len-1)
    {
        j=i;
        while(j<len-1)
         {
             k=i+1;
             x=j-i+1;
             if(x<=max)
                 c=c+len-k-x+1;
             else
                while(k+x<=len)
                {
                  if(strncmp(input+i,input+k,x+1)==0)
                   {
                      if(max>=0)
                          c=c+x;
                   }
                  else
                   c+=calcMis(input,i,k,x);
                  k=k+1;
                }       
            j=j+1;
         }
        i=i+1;
    }   
    printf("%d",c);
    return 0;   
}  

这段代码是问题的解决方案:

Given a string S and and integer K, find the integer C which equals the number of pairs of substrings(S1,S2) such that S1 and S2 have equal length and Mismatch(S1, S2) <= K where the mismatch function is defined below.

例如:abc 那么子串是{a,ab,abc,b,b​​c,c}

还有比这更好的方法吗？这段代码是否有任何可能的优化？

Answer 1

这是一个可能有用的想法。首先，比较字符串中的所有字符对:

void compare_all(char* string, int length, int* comp)
{
    for (int i1 = 0; i1 < length; ++i1)
        for (int i2 = 0; i2 < length; ++i2)
            result[i1 * length + i2] = (string[i1] != string[i2]);
}

这里 comp 表示包含值 0 和 1 的方阵。每对子字符串对应于该矩阵中的对角线部分。例如，对于字符串“testing”，矩阵的以下部分表示子字符串“tes”和“tin”。

. . . O . . .
. . . . O . .
. . . . . O .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .

您必须计算有多少部分的元素总和不超过 k。为此，请一条一条地检查所有与主对角线平行的对角线。为了不重复计算事物，只看那些低于(或高于)主对角线的事物(为简单起见，让我们包括主对角线)。

int count_stuff(int* comp, int n, int k)
{
    int result = 0;
    for (diag = 0; diag < n; ++diag)
    {
        int* first_element_in_diagonal = comp + diag;
        int jump_to_next_element = n + 1;
        int length_of_diagonal = n - diag;
        result += count_stuff_on_diagonal(
            first_element_in_diagonal,
            jump_to_next_element,
            length_of_diagonal,
            k);
    }
    return result;
}

现在，问题要简单得多:找到整数序列的部分数，这些部分的总和不大于 k。最直接的方法是枚举所有此类部分。

int count_stuff_on_diagonal(int* comp, int jump, int n, int k)
{
    int result = 0;
    for (int i1 = 0; i1 < n; ++i1)
        for (int i2 = i1 + 1; i2 < n; ++i2)
        {
            int* first_element_in_section = comp + i1 * jump;
            int mismatches = count_sum_of_section(
                first_element_in_section,
                jump,
                i2 - i1);
            if (mismatches <= k)
                ++result;
        }
    return result;
}

为了提高计算一段连续整数的总和的速度，构建一个 cumulative sums 的表;在 0 和 1 的矩阵上使用它。

(请原谅我没有使用const和VLA，偶尔会出现语法错误)。