1

对于两个字符串 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);
    }
}

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

4

2 回答 2

2

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

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

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

  1. l现在，取字符串中的第一个字母s，并使用一次二分查找查找以i开头的后缀数组中的第一个字符串的索引l，并使用另一个二分查找查找j范围 [i..n 中的第一个字符串的索引]，它不以l. 然后，您将拥有 [i..j-1] 范围内的所有字符串都以相同的字母开头l。所以问题的答案至少是ji。

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

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

于 2012-01-15T10:16:08.317 回答
1

您在评论中提到它是正确的，但是速度很慢。

String在Java中，你可以用with来获取a的长度s.length()——这个值被缓存在对象中，它就是O(1)要获取的。

但是当你转到 C 时，你会得到一个字符串的长度，每次都会用strlen(s)它重新计算 (in )。O(n)所以当你应该做的时候O(n)，因为你O(n)在那里有一个操作，整个函数变成了O(n^2).

要解决此问题，请在运行时缓存该值一次。这会让你回到线性时间。

坏的：

scanf("%s",s);
for(i=0;i<strlen(s);i++)
    if(s[i]==s[0])
    {
        sum=sum+getSim(s,i);
    }

好的：

scanf("%s",s);
strlen = strlen(s); /* assume you declared "int strlen" earlier */
for(i=0;i<strlen;i++) /* this is now constant time to run */
    if(s[i]==s[0])
    {
        sum=sum+getSim(s,i);
    }
于 2012-01-15T09:55:01.703 回答