Introduction
A simple example that uses the parallel_for template in a substring matching program. For each position in a string, the program displays the length of the largest matching substring elsewhere in the string. The program also displays the location of a largest match for each position. Consider the string "babba" as an example. Starting at position 0, "ba" is the largest substring with a match elsewhere in the string (position 3).
==============================================================================
Copyright 2005-2006 Intel Corporation. All Rights Reserved.
==============================================================================
#include "iostream"
#include "string"
#include "algorithm"
#include "tbb/task_scheduler_init.h"
#include "tbb/parallel_for.h"
#include "tbb/blocked_range.h"
using namespace tbb;
using namespace std;
static const size_t N = 23;
class SubStringFinder {
const string str;
size_t *max_array;
size_t *pos_array;
public:
void operator() ( const blocked_range r ) const {
for ( size_t i = r.begin(); i != r.end(); ++i ) {
size_t max_size = 0, max_pos = 0;
for (size_t j = 0; j < str.size(); ++j)
if (j != i) {
size_t limit = str.size()-( i > j ? i : j );
for (size_t k = 0; k < limit; ++k) {
if (str[i + k] != str[j + k]) break;
if (k > max_size) {
max_size = k;
max_pos = j;
}
}
}
max_array[i] = max_size;
pos_array[i] = max_pos;
}
}
SubStringFinder(string &s, size_t *m, size_t *p) :
str(s), max_array(m), pos_array(p) { }
};
int main(size_t argc, char *argv[]) {
task_scheduler_init init;
string str[N] = { string("a"), string("b") };
for (size_t i = 2; i < N; ++i) str[i] = str[i-1]+str[i-2];
string &to_scan = str[N-1];
size_t *max = new size_t[to_scan.size()];
size_t *pos = new size_t[to_scan.size()];
parallel_for(blocked_range(0, to_scan.size(), 100),
SubStringFinder( to_scan, max, pos ) );
for (size_t i = 0; i < to_scan.size(); ++i)
cout << " " << (int)max[i] << "(" << (int)pos[i] << ")" << endl;
return 0;
}
|
