attaboy182
BAN USER@Norman For the worst case, I am afraid so. This be the complexity of find() (source: cpluscplus)
"Unspecified, but generally up to linear in length()-pos times the length of the sequence to match (worst case)."
Just another c++ implementation where each cell is visited only once. Cheers.
{
#include <iostream>
using namespace std;
#define WIDTH 5
#define HEIGHT 5
void findPattern(char givenArray[][HEIGHT], std::string pattern){
std::size_t found;
for (int i=0; i<WIDTH;i++){
for(int j=0; j<HEIGHT;j++){
found = pattern.find(givenArray[i][j]);
if(found!=std::string::npos){
pattern.erase(pattern.begin()+found);
}
}
}
if(pattern.empty()) cout<<"pattern found"<<endl;
else cout << "pattern not found, number of unmatched characters: "<<pattern.length()<<endl;
}
int main() {
char givenArray[WIDTH][HEIGHT] ={{'a','b','c','r','d'},
{'e','f','o','g','h'},
{'i','o','j','k','i'},
{'w','g','f','m','n'},
{'z','a','s','i','t'}};
std::string pattern = "microsoft";
findPattern(givenArray, pattern);
return 0;
}
}
- attaboy182 September 19, 2013
If the total number of distinct characters is 2, then why can't we just XOR each pair in pattern and compare with the XOR of the corresponding pair in the input? Wouldn't that be plain O(n) ?
- attaboy182 December 21, 2016