c - c中的字符串相似度

Question

对于两个字符串 A 和 B，我们将字符串的相似度定义为两个字符串共有的最长前缀的长度。例如，字符串“abc”和“abd”的相似度为2，而字符串“aaa”和“aaab”的相似度为3。计算字符串S与其每一个后缀的相似度之和

这是我的解决方案...

#include<stdio.h>
#include<string.h>
int getSim(char str[],int subindex)
{
    int l2=subindex
    int i=0;
    int count=0;
    for(i=0;i<l2;i++)
        if(str[i]==str[subindex])
        {
            count++;
            subindex++;
        }
        else
            break;
    return count;   
}
int main()
{
    int testcase=0;
    int len=0;
    int sum=0;
    int i=0;
    char s[100000];
    scanf("%d",&testcase);
    while(testcase--)
    {
        sum=0;
        scanf("%s",s);
        for(i=0;i<strlen(s);i++)
            if(s[i]==s[0])
            {
                sum=sum+getSim(s,i);
            }
        printf("%d\n",sum);
    }
}

我们如何使用后缀数组来解决这个问题？

Answer 1

我不确定这是否是最好的算法，但这是解决方案。

首先，建立后缀数组。天真的算法(将所有后缀放入数组然后对其进行排序)非常慢 - O(n^2 * log(n)) 操作，有几种算法可以在 O(nlogn) 时间内完成此操作。

我假设字符串是从 0 开始索引的。

1. 现在，取字符串s中的第一个字母l，并使用一次二分查找找到索引i后缀数组中以 l 开头的第一个字符串，以及另一个二进制搜索以查找范围 [i..n] 中第一个字符串的索引 j，这不'以 l 开头。然后你会得到 [i..j-1] 范围内的所有字符串都以相同的字母 l 开头。所以问题的答案至少是j-i。

2. 然后对 [i..j) 范围内的字符串应用类似的过程。取第二个字母l2，找到第一个字符串s[i2]对应的索引i2和j2使得s[i2][1] == l2 和第一个字符串 s[j2] 使得 s[j2][1] != l2。将 j2-i2 添加到答案中。

3. 重复此过程 n 次，直到用完原始字符串中的字母。问题的答案是j1-i1 + j2-i2 + ... + jn-in