fork download
copy 
  1. /*
  2.   Copyright 2013 Marek "p2004a" Rusinowski
  3.   Dictionary of basic factors
  4. */
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <vector>
  8. #include <utility>
  9. #include <map>
  10.  
  11. using namespace std;
  12.  
  13. class DBF {
  14.   vector<vector<int> > t;
  15.   int max_len;
  16.  public:
  17.  
  18.   explicit DBF(const char *str) {
  19.     int len = strlen(str);
  20.     t.push_back(vector<int>());
  21.     t[0].resize(len);
  22.     for (int i = 0; i < len; ++i) {
  23.       t[0][i] = str[i];
  24.     }
  25.     for (int k = 0, width = 1; width < len; ++k, width <<= 1) {
  26.       map<pair<int, int>, int> pairs;
  27.       for (int i = 0; i < len - width; ++i) {
  28.         pairs[make_pair(t[k][i], t[k][i + width])] = i;
  29.       }
  30.       if ((int) pairs.size() == len - width) {
  31.         max_len = (width << 1) - 1;
  32.         break;
  33.       }
  34.       t.push_back(vector<int>());
  35.       t[k + 1].resize(len - width);
  36.       for (int i = 0; i < len - width; ++i) {
  37.         t[k + 1][i] = pairs[make_pair(t[k][i], t[k][i + width])];
  38.       }
  39.     }
  40.   }
  41.  
  42.   bool cmp(int beg1, int beg2, int len) {
  43.     if (beg1 == beg2) return true;
  44.     if (len > max_len) return false;
  45.     int i = 0;
  46.     while (1 << (i + 1) < len) ++i;
  47.     return t[i][beg1] == t[i][beg2] 
  48.      && t[i][beg1 + len - (1 << i)] == t[i][beg2 + len - (1 << i)];
  49.   }
  50. };
  51.  
  52. int main() {
  53.   DBF dbf("abbaabbabababbaaaba");
  54.   printf("%s\n", dbf.cmp(3, 15, 3) ? "tak" : "nie");
  55.   printf("%s\n", dbf.cmp(3, 15, 4) ? "tak" : "nie");
  56.   return 0;
  57. }
  58.  
Success #stdin #stdout 0s 2992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
tak
nie
https://ideone.com/O3LIuQ
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!