1

X是否有一种有效的算法来计算较长字符串中子字符串的出现总数Y？

更具体地说，我想要的是从 B 中选择 A.size() 元素的方式总数，使得存在与 B 匹配的所选元素的排列。

一个例子如下：搜索X=AB字符串中出现的总次数Y=ABCDBFGHIJ？

答案是 2：第一个 A 和第二个 B，以及第一个 A 和第 5 个 B。

我知道我们可以生成长字符串的所有排列（将是N!长度N字符串Y）并使用 KMP 算法搜索/计算 in 的X出现Y。

我们能做得更好吗？

我试图解决的原始问题如下：假设我们有一个大小为 r x c 的大矩阵 M（r 和 c 在 10000 的范围内）。给定一个大小为 a x b 的小矩阵 P（a 和 b 在 10 的范围内）。求 M 的 a 行和 b 列的不同选择的总数（这将给我们一个 a 乘 b “子矩阵”H），这样就存在 H 的行和列的置换，这给我们一个匹配 P 的矩阵.

我认为一旦我可以解决一维案例，二维可能会遵循解决方案。

经过研究，我发现这是一个子图同构问题，并且是 NP 难的。有一些算法可以有效地解决这个问题。人们可以谷歌它并看到许多关于此的论文。

4

2 回答 2

1

阅读后，然后重新阅读问题（在@Charlie 的建议下），我得出结论，这些答案并没有解决真正的问题。我还得出结论，我仍然不知道确切的问题是什么，但如果 OP 回答了我的问题并澄清了问题，那么我会回来并更好地尝试解决它。现在，我将把它作为一个占位符......

要查找出现的字母或其他字符： 

char buf[]="this is the string to search";
int i, count=0, len;
len = strlen(buf);
for(i=0;i<len;i++)
{
    if(buf[i] == 's') count++;
}

或者，使用strtok()，查找子字符串的出现：
不漂亮，蛮力方法。
// 要搜索的字符串

char str1[]="is";
char str2[]="s";
int count = 0;
char buf[]="this is the string to search";
char *tok;
tok = strtok(buf, str1);
while(tok){
    count++;
    tok = strtok(NULL, str1);
}
tok = strtok(buf, str2);
while(tok){
    count++;
    tok = strtok(NULL, str2);
}

count 应该包含“s”的出现次数，+“is”的出现次数

[编辑]
首先，让我要求对您的问题进行技术澄清，给定 A =“AR”，B =“START”，解决方案将是“A”，“R”和“AR”，在这种情况下都找到了在 B 的第 3 和第 4 个字母中。正确吗？如果是这样，那就很容易了。您可以通过对我上面已经完成的操作进行一些小的修改和添加来做到这一点。如果您对该代码有任何疑问，如果可以的话，我很乐意解决。

第二部分是您真正的问题：搜索比 KMP 算法更好，或者至少具有与KMP 算法相同的效率——这才是真正的技巧。如果选择最好的方法是真正的问题，那么一些谷歌搜索是正确的。因为一旦你找到并确定了解决子字符串搜索的最佳方法（效率 >= KPM），那么实现将是一组简单的步骤（如果你给它足够的时间)，可能但不一定使用上面使用的 C 的某些相同组件。（我认为指针操作会比使用字符串函数更快。）但是这些技术只是实现，应该始终遵循良好的设计。以下是一些 Google 搜索，可帮助您开始搜索……（您可能已经去过其中的一些）

验证 KMP
KMP - 我们能做得更好吗？
KMP - 定义
的 KMP - 使用斐波那契字符串的改进

如果您在选择算法并开始实施您的设计后，对技术或编码建议有疑问，请发布它们。我的猜测是这里有几个人会喜欢帮助使用这种有用的算法。

于 2013-10-15T19:43:44.637 回答
0

如果 X 是 Y 中的子字符串，则 X 的每个字符都必须在 Y 中。所以我们首先遍历 X 并在数组中找到每个字符的计数counts。

然后对于每个具有 的字符count >= 1，我们计算它出现的次数，Y可以在 中轻松完成O(n)。

从这里开始，答案应该只是组合的乘法C(count(Y),count(X))。

如果在第三次阅读您的问题后，我终于正确理解了它。

于 2013-10-16T00:11:05.997 回答