2

给定一个字符串和字符串数组，找出数组中字符串的最长后缀。

例如

字符串 =google.com.tr

数组 =tr, nic.tr, gov.nic.tr, org.tr, com.tr

返回com.tr

我曾尝试使用带有特定比较器的二进制搜索，但失败了。

C代码将受到欢迎。

编辑：

我应该说我正在寻找一个解决方案，我可以在准备步骤中做尽可能多的工作（当我只有一组后缀，并且我可以以各种可能的方式对其进行排序时，围绕它构建任何数据结构等等），并且对于给定的字符串，尽可能快地在这个数组中找到它的后缀。我也知道我可以从这个数组中构建一个 trie，这可能会给我最好的性能，但是我非常懒惰，并且在纠结的企业代码中保持一个原始 C 中的 trie 一点也不好玩。所以一些类似 binsearch 的方法将非常受欢迎。

4

5 回答 5

1

假设字符串中字符的时间寻址是恒定的，这个问题与寻找最大前缀是同构的。

  1. 让i = 0.

  2. 让S = null

  3. 让c = prefix[i]

  4. a从Aifa[i] != c和 if中删除字符串A。替换S为aif a.Length == i + 1。

  5. 增量i。

  6. 转到第 3 步。

那是你要找的吗？

例子：

前缀 = rt.moc.elgoog

数组 = rt.moc、rt.org、rt.cin.vof、rt.cin、rt

Pass 0: prefix[0]is 'r'and array[j][0] == 'r'for allj所以没有从数组中删除。 i + 1 -> 0 + 1 -> 1是我们的目标长度，但没有一个字符串的长度为 1，所以S仍然是null.

Pass 1: prefix[1]is 't'and array[j][1] == 'r'for allj所以没有从数组中删除。但是，有一个长度为 2 的字符串，因此S变为rt。

Pass 2: prefix[2]is '.'andarray[j][2] == '.'对于其余的字符串，所以没有任何变化。

Pass 3: prefix[3]is'm'和array[j][3] != 'm'for rt.org, rt.cin.vof, 等rt.cin这些字符串被删除。

等等

于 2013-08-26T08:23:45.487 回答
0

为什么不使用后缀数组？当您有大量后缀时，它可以工作。

复杂性，O(n(logn)^2)也有O(nlogn)版本。

在这里用 c 实现。您也可以尝试使用谷歌搜索后缀数组。

于 2013-08-26T12:36:33.983 回答
0

另一个天真的伪答案。

将布尔值“找到”设置为 false。当“found”为假时，迭代数组，将源字符串与数组中的字符串进行比较。如果匹配，将“found”设置为 true 并中断。如果没有匹配项，请使用类似strchr()的方法来获取第一个句点之后的字符串段。再次遍历数组。继续直到有一个匹配，或者直到源字符串的最后一段已与数组中的所有字符串进行比较并且匹配失败。

效率不是很高......

于 2013-08-26T08:19:55.677 回答
0

天真，伪答案：

  1. 按长度对后缀数组进行排序（是的，可能有相同长度的字符串，我认为这是您提出的问题的问题）
  2. 遍历数组并查看后缀是否在给定字符串中
  3. 如果是，退出循环，因为你已经完成了！如果没有，请继续。

或者，您可以跳过排序并进行迭代，分配biggestStringifcurrentString大于biggestString匹配的。

编辑0：

也许您可以通过事先查看您的数组并考虑需要检查的“最小”元素来改进这一点。

例如，如果.com出现在 20 个成员中，您可以只检查.com给定的字符串以潜在地消除 20 个候选人。

编辑1：

再三考虑，为了比较数组中的元素，您需要使用字符串比较。我的感觉是，尝试优化字符串列表以进行比较而获得的任何收益都可能会被在这样做之前比较它们的代价所抵消，如果这是有道理的话。如果CS类型可以在这里纠正我，将不胜感激......

于 2013-08-26T08:07:15.787 回答
0

如果您的字符串数组如下所示：

char string[STRINGS][MAX_STRING_LENGTH];
string[0]="google.com.tr";
string[1]="nic.tr";

等等，那么你可以简单地这样做：

int x, max = 0;

for (x = 0; x < STRINGS; x++) {
    if (strlen(string[x]) > max) {
        max = strlen(string[x]);
    }
}

x = 0;

while(true) {
    if (string[max][x] == ".") {
       GOTO out;
    }
    x++;
}

out:

char output[MAX_STRING_LENGTH];
int y = 0;

while (string[max][x] != NULL) {
    output[y++] = string[++x];
}

（上面的代码可能实际上不起作用（错误等），但您应该了解总体思路。

于 2013-08-26T08:44:55.553 回答