Intel Threading Building Blocks

SubstringFinder

SubstringFinder uses the parallel_for template in a substring matching program. For each position in a string, the program finds the length and location of the largest matching substring elsewhere in the string. For instance, take the string OregonOrmereg. Starting a scan at the first character (position 0), the largest substring with a match elsewhere in the string is Or at position 6. Starting at position 1, the largest match is reg at position 10. The position of such matches, and the length of the match, is recorded for every position in the string being searched.

Example 11-9 shows a serial version (lines 12–31) and a parallel version (lines 33–55). Note how lines 15–31 and 39–55 are nearly identical. The only difference is that the serial version does all the work directly on the input array, whereas the parallel version works on a range passed to it in the blocked_range r. For the sake of simplicity, both versions declare an array of static size to hold the output.

Example 11-9. Serial and parallel SubstringFinder

 1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include "tbb/task_scheduler_init.h" 5 #include "tbb/parallel_for.h" 6 #include "tbb/blocked_range.h" 7 #include "tbb/tick_count.h" 8 using namespace tbb; 9 using namespace std; 10 static const size_t N = 22; 11 12 void SerialSubStringFinder ( const string &str, 13 size_t *max_array, 14 size_t *pos_array) { 15 for ( size_t i = 0; i < str.size(); ++i ) { 16 size_t max_size = 0, max_pos ...