Essentially you can slide a window of the length of your word over your input and keep a count of how many of each letter are in the window. When the letter counts in your sliding window match the letter counts of your word, you have a match.
Let your word length be n
, and your current position be curr
. Create an array, or vector
, windCounts
of length 26. The entry windCounts[i]
stores the number of occurrences of the ith letter of the alphabet seen from position curr - n - 1
to curr
.
What you do is you advance curr
, and keep your array windCounts
up to date, by decrementing the letter that has dropped out of the back of the sliding window, and incrementing the letter count that has appeared in the front of the sliding window. (Obviously until curr
> n
, you only increment, you just build up your sliding window to the length of your word.)
In C++, you can use a vector
for the counts of letters in your word, and for the counts of letters in your sliding window and simply use vector::operator==
to do the equality.
Edit: the algorithm is O(N)
, where N
is the length of the text to search. This can be seen from the code below where the loop body is executed for each letter that you slide the window.
#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;
}
forxxorfxdofr
x are separators?forf
? 2 or 1.