https://gitweb.dealii.org/ - dealii-svn.git/blob

   1 /*
   2     Copyright 2005-2013 Intel Corporation.  All Rights Reserved.
   3
   4     This file is part of Threading Building Blocks.
   5
   6     Threading Building Blocks is free software; you can redistribute it
   7     and/or modify it under the terms of the GNU General Public License
   8     version 2 as published by the Free Software Foundation.
   9
  10     Threading Building Blocks is distributed in the hope that it will be
  11     useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  12     of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with Threading Building Blocks; if not, write to the Free Software
  17     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18
  19     As a special exception, you may use this file as part of a free software
  20     library without restriction.  Specifically, if other files instantiate
  21     templates or use macros or inline functions from this file, or you compile
  22     this file and link it with other files to produce an executable, this
  23     file does not by itself cause the resulting executable to be covered by
  24     the GNU General Public License.  This exception does not however
  25     invalidate any other reasons why the executable file might be covered by
  26     the GNU General Public License.
  27 */
  28
  29 #include <iostream>
  30 #include <string>
  31 #include <algorithm>
  32
  33 #include "tbb/parallel_for.h"
  34 #include "tbb/blocked_range.h"
  35
  36 using namespace tbb;
  37 static const size_t N = 9;
  38
  39 class SubStringFinder {
  40  const std::string str;
  41  size_t *max_array;
  42  size_t *pos_array;
  43  public:
  44  void operator() ( const blocked_range<size_t>& r ) const {
  45   for ( size_t i = r.begin(); i != r.end(); ++i ) {
  46    size_t max_size = 0, max_pos = 0;
  47    for (size_t j = 0; j < str.size(); ++j)
  48     if (j != i) {
  49      size_t limit = str.size()-( i > j ? i : j );
  50      for (size_t k = 0; k < limit; ++k) {
  51       if (str[i + k] != str[j + k]) break;
  52       if (k+1 > max_size) {
  53        max_size = k+1;
  54        max_pos = j;
  55       }
  56      }
  57     }
  58    max_array[i] = max_size;
  59    pos_array[i] = max_pos;
  60   }
  61  }
  62  SubStringFinder(std::string &s, size_t *m, size_t *p) :
  63   str(s), max_array(m), pos_array(p) { }
  64 };
  65
  66 int main(int argc, char *argv[]) {
  67
  68
  69  std::string str[N] = { std::string("a"), std::string("b") };
  70  for (size_t i = 2; i < N; ++i) str[i] = str[i-1]+str[i-2];
  71  std::string &to_scan = str[N-1];
  72  size_t num_elem = to_scan.size();
  73  std::cout << "String to scan: " << to_scan << std::endl;
  74
  75  size_t *max = new size_t[num_elem];
  76  size_t *pos = new size_t[num_elem];
  77
  78  parallel_for(blocked_range<size_t>(0, num_elem, 100),
  79        SubStringFinder( to_scan, max, pos ) );
  80
  81  for (size_t i = 0; i < num_elem; ++i) {
  82    for (size_t j = 0; j < num_elem; ++j) {
  83      if (j >= i && j < i + max[i]) std::cout << "_";
  84      else std::cout << " ";
  85    }
  86    std::cout << std::endl << to_scan << std::endl;
  87
  88    for (size_t j = 0; j < num_elem; ++j) {
  89      if (j >= pos[i] && j < pos[i] + max[i]) std::cout << "*";
  90      else std::cout << " ";
  91    }
  92    std::cout << std::endl;
  93  }
  94  delete[] max;
  95  delete[] pos;
  96  return 0;
  97 }
  98