给定一个单词和一个文本，返回文本中单词的字谜出现次数。例如。单词是“for”，文本是“forxxorfxdofr”，“for”的字谜将是“ofr”、“orf”、“fro”等。所以对于这个特定的例子，答案是 3。
我有蛮力方法，它获取单词的所有排列，然后比较文本是否包含它，并增加出现次数，但这是 O(N^2) 方法。我正在寻找更好的复杂性。
问问题
4287 次
5 回答
15
您可以简单地查找字符数。
例如，假设您正在寻找look. 因此，您正在寻找：
- 一个 4 字符长度的单词，
- 有 1 l、2 o 和 1 k。
只需处理前 4 个字母，存储计数。检查是否有匹配项。添加下一个字符（增量），删除旧字符（减量）。再检查一遍。等等...
于 2013-09-15T11:09:06.673 回答
3
TooTone 的 O( n ) 解决方案必须为输入文本的每个字符比较两个 256 元素向量。这可以通过跟踪两个向量不同的位置的数量来避免，并在该数量变为零时记录匹配。事实上，我们甚至根本不需要存储两个不同的向量，因为我们可以只存储一个包含它们差异的向量。
这是我实现这些优化的版本。它是用普通的旧 C 语言编写的，但应该在 C++ 下进行适当的调整：
#include <stdio.h>
#include <limits.h> /* for UCHAR_MAX (usually 255) */
int find_anagrams (char *word, char *text) {
int len = 0; /* length of search word */
int bin[UCHAR_MAX+1]; /* excess count of each char in last len chars of text */
int mismatch = 0; /* count of nonzero values in bins[] */
int found = 0; /* number of anagrams found */
int i; /* generic loop counter */
/* initialize bins */
for (i = 0; i <= UCHAR_MAX; i++) bin[i] = 0;
for (i = 0; word[i] != '\0'; i++) {
unsigned char c = (unsigned char) word[i];
if (bin[c] == 0) mismatch++;
bin[c]--;
len++; /* who needs strlen()? */
}
/* iterate through text */
for (i = 0; text[i] != '\0'; i++) {
/* add next char in text to bins, keep track of mismatch count */
unsigned char c = (unsigned char) text[i];
if (bin[c] == 0) mismatch++;
if (bin[c] == -1) mismatch--;
bin[c]++;
/* remove len-th previous char from bins, keep track of mismatch count */
if (i >= len) {
unsigned char d = (unsigned char) text[i - len];
if (bin[d] == 0) mismatch++;
if (bin[d] == 1) mismatch--;
bin[d]--;
}
/* if mismatch count is zero, we've found an anagram */
if (mismatch == 0) {
found++;
#ifdef DEBUG
/* optional: print each anagram found */
printf("Anagram found at position %d: \"", i-len+1);
fwrite(text+i-len+1, 1, len, stdout);
printf("\"\n");
#endif
}
}
return found;
}
int main (int argc, char *argv[]) {
if (argc == 3) {
int n = find_anagrams(argv[1], argv[2]);
printf("Found %d anagrams of \"%s\" in \"%s\".\n", n, argv[1], argv[2]);
return 0;
} else {
fprintf(stderr, "Usage: %s <word> <text>\n", (argc ? argv[0] : "countanagrams"));
return 1;
}
}
于 2013-09-15T18:08:56.170 回答
2
本质上，您可以在输入内容上滑动一个单词长度的窗口，并计算窗口中每个字母的数量。当滑动窗口中的字母计数与单词的字母计数匹配时，您就有了匹配项。
让你的字长是n，你现在的位置是curr。创建一个长度为 26 的数组或 。该条目vector存储从位置到看到的字母表中第 i个字母的出现次数。windCountswindCounts[i]curr - n - 1curr
您所做的是通过减少从滑动窗口后面掉出的字母并增加出现在滑动窗口前面的字母计数来推进curr并保持数组最新。windCounts（显然，直到curr> n，你只会增加，你只是建立你的滑动窗口到你的单词的长度。）
在 C++ 中，您可以使用 avector来计算单词中的字母数，以及滑动窗口中的字母数，然后简单地使用vector::operator==来进行相等。
编辑：算法是O(N)，其中N是要搜索的文本的长度。这可以从下面的代码中看出，其中为您滑动窗口的每个字母执行循环体。
#include <string>
#include <vector>
#include <algorithm> // for_each
using std::string;
using std::vector;
#include <iostream>
int main(int argc, char* argv[])
{
const string text = "forxxorfxdofr";
const string word = "for";
// Counts of letters in word
vector<int> wordCounts(256); // optimization: cut down from 256 to 26
std::for_each(word.begin(), word.end(),
[&] (char c) { wordCounts[c]++; } );
// Current position of end of sliding window
string::const_iterator curr = text.begin() + word.size();
// Initial sliding window counts
vector<int> windCounts(256);
std::for_each(text.begin(), curr,
[&] (char c) { windCounts[c]++; } );
// Run sliding window over text
int numMatches = 0;
while (1) {
numMatches += wordCounts == windCounts;
if (curr == text.end()) {
break;
}
windCounts[*(curr - word.size())]--;
windCounts[*curr]++;
++curr;
}
std::cout << numMatches << "\n";
return 0;
}
于 2013-09-15T11:10:29.003 回答
0
我取了两个字符串，即str和occ。Str 是原始字符串，occ 是我们必须找出计数的字符串。使用 strncpy 函数，我将 occ 即 n 字符的长度复制到一个临时数组中，然后检查它是否是 occ 字符串的排列。
#include<iostream.h>
#include<conio.h>
#include<string.h>
int permutate(char str1[],char str2[]);
int permutate(char str1[],char str2[]) {
int c[256]={0},i,j;
for(i=0;i<strlen(str1);i++)
c[str1[i]]++;
for(i=0;i<strlen(str2);i++) {
c[str2[i]]--;
if(c[str2[i]]<0)
return 1; //not a permutation
}
return 0; //permutation
}
int main() {
//enter code here
char str[]="forxxorfxdofr",occ[]="for",temp[10];
int n,i,x,t=0;
n=strlen(occ);
for(i=0;i<strlen(str);i++) {
strncpy(temp,str+i,n); //copy the n char from str to temp
x=permutate(temp,occ);
if(x==0) //if string is a permutation
t++;
}
cout<<"Count = " << t;
return 0;
}
于 2013-09-20T10:30:57.897 回答
0
o(n) solution in Python
定义检查（s1，s2）：
function takes in s1 as the text and s2 as the text to be checked from here for
c=0
n=len(s2)
ck=sorted(s2)
mk=''.join(ck)
this loop will pick from s till the length of s2 that is 'for'
for i,item in enumerate(s1):
if s1[i] in mk:
p=s1[i:i+n]
jk=sorted(p)
er=''.join(jk)
now just comparing the both sorted strings if they are equal then they were anagram
if er == mk:
c+=1
return c
于 2020-09-12T21:42:25.293 回答