fork(3) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <ctime>
  4. #include <random>
  5. #include <algorithm>    // std::min
  6.  
  7. using namespace std;
  8.  
  9. const int MAX_N = 5000;
  10.  
  11. int seg[2 * MAX_N];
  12. int segsL[MAX_N][2 * MAX_N];
  13. int m[MAX_N][MAX_N][2];
  14. int dp[MAX_N][MAX_N];
  15. int best;
  16.  
  17. // Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
  18. void update(int n, int p, int value) { // set value at position p
  19.   for (seg[p += n] = value; p > 1; p >>= 1)
  20.     seg[p >> 1] = seg[p] + seg[p ^ 1];
  21. }
  22. // Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
  23. int query(int n, int l, int r) { // sum on interval [l, r)
  24.   int res = 0;
  25.   for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  26.     if (l & 1) res += seg[l++];
  27.     if (r & 1) res += seg[--r];
  28.   }
  29.   return res;
  30. }
  31. // Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
  32. void updateL(int n, int i, int p, int value) { // set value at position p
  33.   for (segsL[i][p += n] = value; p > 1; p >>= 1)
  34.     segsL[i][p >> 1] = segsL[i][p] + segsL[i][p ^ 1];
  35. }
  36. // Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
  37. int queryL(int n, int i, int l, int r) { // sum on interval [l, r)
  38.   int res = 0;
  39.   for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  40.     if (l & 1) res += segsL[i][l++];
  41.     if (r & 1) res += segsL[i][--r];
  42.   }
  43.   return res;
  44. }
  45.  
  46. // Code by גלעד ברקן
  47. void precalc(int n, string & s) {
  48.   int i, j;
  49.   for (i = 0; i < n; i++) {
  50.     for (j = 0; j < n; j++) {
  51.       // [longest match left, longest match right]
  52.       m[i][j][0] = (s[i] == s[j]) & 1;
  53.       m[i][j][1] = (s[i] == s[j]) & 1;
  54.     }
  55.   }
  56.  
  57.   for (i = n - 2; i >= 0; i--)
  58.     for (j = n - 2; j >= 0; j--)
  59.       m[i][j][1] = s[i] == s[j] ? 1 + m[i + 1][j + 1][1] : 0;
  60.  
  61.   for (i = 1; i < n; i++)
  62.     for (j = 1; j < n; j++)
  63.       m[i][j][0] = s[i] == s[j] ? 1 + m[i - 1][j - 1][0] : 0;
  64. }
  65.  
  66. // Code by גלעד ברקן
  67. void f(int n, string & s) {
  68.   int i, j, k, longest;
  69.  
  70.   dp[0][n - 1] = 1;
  71.   update(n, n - 1, 1);
  72.   updateL(n, n - 1, 0, 1);
  73.  
  74.   // Right side initialisation
  75.   for (j = n - 2; j >= 0; j--) {
  76.     if (s[0] == s[j + 1]) {
  77.       longest = std::min(j + 1, m[0][j + 1][1]);
  78.       for (k = j + 1; k <= j + longest; k++)
  79.         dp[0][j] |= dp[0][k];
  80.       if (dp[0][j]) {
  81.         update(n, j, 1);
  82.         updateL(n, j, 0, 1);
  83.         best = std::min(best, j + 1);
  84.       }
  85.     }
  86.   }
  87.  
  88.   // Left side initialisation
  89.   for (i = 1; i < n; i++) {
  90.     if (s[i - 1] == s[n - 1]) {
  91.       // We are bound by the current range
  92.       longest = std::min(n - i, m[i - 1][n - 1][0]);
  93.       for (k = i - 1; k >= i - longest; k--)
  94.         dp[i][n - 1] |= dp[k][n - 1];
  95.       if (dp[i][n - 1]) {
  96.         updateL(n, n - 1, i, 1);
  97.         best = std::min(best, n - i);
  98.       }
  99.     }
  100.   }
  101.  
  102.   for (i = 1; i <= n - 2; i++) {
  103.     for (int ii = 0; ii < MAX_N; ii++) {
  104.       seg[ii * 2] = 0;
  105.       seg[ii * 2 + 1] = 0;
  106.     }
  107.     update(n, n - 1, dp[i][n - 1]);
  108.     for (j = n - 2; j >= i; j--) {
  109.       // We removed on the right
  110.       if (s[i] == s[j + 1]) {
  111.         // We are bound by half the current range
  112.         longest = std::min(j - i + 1, m[i][j + 1][1]);
  113.         //for (k=j+1; k<=j+longest; k++)
  114.         //dp[i][j] |= dp[i][k];
  115.         if (query(n, j + 1, j + longest + 1)) {
  116.           dp[i][j] = 1;
  117.           update(n, j, 1);
  118.           updateL(n, j, i, 1);
  119.         }
  120.       }
  121.       // We removed on the left
  122.       if (s[i - 1] == s[j]) {
  123.         // We are bound by half the current range
  124.         longest = std::min(j - i + 1, m[i - 1][j][0]);
  125.         //for (k=i-1; k>=i-longest; k--)
  126.         //dp[i][j] |= dp[k][j];
  127.         if (queryL(n, j, i - longest, i)) {
  128.           dp[i][j] = 1;
  129.           updateL(n, j, i, 1);
  130.           update(n, j, 1);
  131.         }
  132.       }
  133.       if (dp[i][j])
  134.         best = std::min(best, j - i + 1);
  135.     }
  136.   }
  137. }
  138.  
  139. int so(string s) {
  140.   for (int i = 0; i < MAX_N; i++) {
  141.     seg[i * 2] = 0;
  142.     seg[i * 2 + 1] = 0;
  143.     for (int j = 0; j < MAX_N; j++) {
  144.       segsL[i][j * 2] = 0;
  145.       segsL[i][j * 2 + 1] = 0;
  146.       m[i][j][0] = 0;
  147.       m[i][j][1] = 0;
  148.       dp[i][j] = 0;
  149.     }
  150.   }
  151.   int n = s.length();
  152.   best = n;
  153.   precalc(n, s);
  154.   f(n, s);
  155.   return best;
  156. }
  157. // End code by גלעד ברקן
  158.  
  159. // Code by Bananon  =======================================================================
  160.  
  161. int result;
  162.  
  163. int lps[MAX_N][MAX_N];
  164. bool checked[MAX_N][MAX_N];
  165.  
  166. void check(int start, int length) {
  167.   checked[start][length] = true;
  168.   if (length < result) {
  169.     result = length;
  170.   }
  171.   for (int i = lps[start][length]; i != 0; i = lps[start][i - 1]) {
  172.     int newLength = length - i;
  173.     if (!checked[start][newLength])
  174.       check(start, newLength);
  175.     int newStart = start + i;
  176.     if (!checked[newStart][newLength])
  177.       check(newStart, newLength);
  178.   }
  179. }
  180.  
  181. int my(string str) {
  182.   int n = str.length();
  183.   for (int l = 0; l < n; l++) {
  184.     int subLength = n - l;
  185.     lps[l][0] = 0;
  186.     checked[l][0] = false;
  187.     for (int i = 1; i < subLength; ++i) {
  188.       int j = lps[l][i - 1];
  189.       while (j > 0 && str[i + l] != str[j + l])
  190.         j = lps[l][j - 1];
  191.       if (str[i + l] == str[j + l]) j++;
  192.       lps[l][i] = j;
  193.       checked[l][i] = false;
  194.     }
  195.   }
  196.   result = n - 1;
  197.   check(0, n - 1);
  198.   return result + 1;
  199. }
  200.  
  201. // generate =================================================================
  202.  
  203. bool rndBool() {
  204.   return rand() % 2 == 0;
  205. }
  206.  
  207. int rnd(int bound) {
  208.   return rand() % bound;
  209. }
  210.  
  211. void untrim(string & str) {
  212.   int length = rnd(str.length());
  213.   int prefixLength = rnd(str.length()) + 1;
  214.   if (rndBool())
  215.     str.append(str.substr(0, prefixLength));
  216.   else {
  217.     string newStr = str.substr(str.length() - prefixLength, prefixLength);
  218.     newStr.append(str);
  219.     str = newStr;
  220.   }
  221. }
  222.  
  223. void rndTest(int minTestLength, string s) {
  224.   while (s.length() < minTestLength)
  225.     untrim(s);
  226.   int myAns = my(s);
  227.   int soAns = so(s);
  228.   cout << myAns << " " << soAns << '\n';
  229.   if (soAns != myAns) {
  230.     cout << s;
  231.     exit(0);
  232.   }
  233. }
  234.  
  235. int main() {
  236.   int minTestLength;
  237.   cin >> minTestLength;
  238.   string seed;
  239.   cin >> seed;
  240.   while (true)
  241.     rndTest(minTestLength, seed);
  242. }
Time limit exceeded #stdin #stdout 5s 491896KB
comments (?)
stdin
copy 
7 abb
stdout
copy 
Standard output is empty
https://ideone.com/pDhxS6
language:
C++ (gcc 8.3)
created:
5 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!