查找字符串中最常见的字符对

Question

我写了以下功能

//O(n^2)
void MostCommonPair(char * cArr , char * ch1 , char * ch2 , int * amount)
{
    int count , max = 0;
    char cCurrent , cCurrent2;
    int i = 0 , j;
    while(*(cArr + i + 1) != '\0')
    {
        cCurrent = *(cArr + i);
        cCurrent2 = *(cArr + i + 1);
        for(j = i , count = 0 ; *(cArr + j + 1) != '\0' ; j++)
        {
            if(cCurrent ==  *(cArr + j) && cCurrent2 ==  *(cArr + j + 1))
            {
                count++;
            }
        }
        if(count > max)
        {
            *ch1 = cCurrent;
            *ch2 = cCurrent2;
            max = *amount = count;
        }
        i++;
    }
}

用于以下输入

"xdshahaalohalobscxbsbsbs"

ch1 = b ch2 = s amount = 4

但在我看来,该功能非常无效,有没有办法只通过字符串一次或将运行大小减少到O(n)？

Answer 1

由于char最多可以容纳256个值,你可以设置[256*256]计数器,通过你的字符串运行一次,递增对应于字符串中的每个字符对的计数器的二维表.然后你可以浏览256x256数字表,选择最大数量,并通过查看它在2D数组中的位置来了解它所属的对.由于计数器表的大小固定为与字符串长度无关的常量值O(1),因此即使需要两个嵌套循环,该操作也是如此.

int count[256][256];
memset(count, 0, sizeof(count));
const char *str = "xdshahaalohalobscxbsbsbs";
for (const char *p = str ; *(p+1) ; p++) {
    count[(int)*p][(int)*(p+1)]++;
}
int bestA = 0, bestB = 0;
for (int i = 0 ; i != 256 ; i++) {
    for (int j = 0 ; j != 256 ; j++) {
        if (count[i][j] > count[bestA][bestB]) {
            bestA = i;
            bestB = j;
        }
    }
}
printf("'%c%c' : %d times\n", bestA, bestB, count[bestA][bestB]);

这是一个关于ideone的演示的链接.

请记住,尽管这是渐近最快的解决方案(即,它O(N)不能使它更快O(N)),性能对于较短的字符串不会有好处.事实上,您的解决方案将在短于大约256个字符的输入上击败它,甚至可能更多.您可以对此代码应用许多优化,但我决定不添加它们以保持代码的主要概念以最纯粹和最简单的形式清晰可见.