c++ - 计算子字符串的出现次数

Question

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

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

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

答案是 2 :第一个 A 第二个 B，以及第一个 A 和第五个 B。

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

我们能做得更好吗？

我尝试解决的原始问题如下:假设我们有一个大小为 r x c 的大矩阵 M(r 和 c 在 10000 的范围内)。给定一个大小为 a 乘以 b 的小矩阵 P(a 和 b 在 10 的范围内)。找到 M 的 a 行和 b 列的不同选择的总数(这将为我们提供一个 a 乘以 b 的“子矩阵”H)，以便存在 H 的行和列的排列，从而为我们提供一个与 P 匹配的矩阵.

我认为一旦我可以解决一维的情况，二维的情况可能会随之而来。

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

Answer 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);
}  

计数应包含“s”出现的总数，+“is”出现的次数

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

第二部分是您的真正问题:搜索效率优于或至少与 KMP algorithm 相同 - 这才是真正的诀窍。如果选择最好的方法是真正的问题，那么一些谷歌搜索是有序的。因为一旦您找到并确定了解决子字符串搜索的最佳方法(效率>= KPM)，那么实现将是一组简单的步骤(if you give it enough time)，可能但不一定使用一些上面使用的 C 的相同组件。 (我认为指针操作会比使用字符串函数更快。)但这些技术只是实现，应该始终遵循良好的设计。以下是一些 Google 搜索，可帮助您开始搜索...(您可能已经使用过其中一些)

Validating KMP
KMP - Can we do better?
KMP - Defined
KMP - Improvements using Fibonacci String

如果您在选择算法并开始实现设计后，对技术或编码建议有疑问，请发布。我猜这里有几个人会乐于帮助开发这样一个有用的算法。