fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>    // std::min
  4.  
  5. using namespace std;
  6.  
  7. const int MAX_N = 5000;
  8.  
  9. int seg[2 * MAX_N];
  10. int segsL[MAX_N][2 * MAX_N];
  11. int m[MAX_N][MAX_N][2];
  12. int dp[MAX_N][MAX_N];
  13. int best;
  14.  
  15. // Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
  16. void update(int n, int p, int value) { // set value at position p
  17.   for (seg[p += n] = value; p > 1; p >>= 1)
  18.     seg[p >> 1] = seg[p] + seg[p ^ 1];
  19. }
  20. // Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
  21. int query(int n, int l, int r) { // sum on interval [l, r)
  22.   int res = 0;
  23.   for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  24.     if (l & 1) res += seg[l++];
  25.     if (r & 1) res += seg[--r];
  26.   }
  27.   return res;
  28. }
  29. // Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
  30. void updateL(int n, int i, int p, int value) { // set value at position p
  31.   for (segsL[i][p += n] = value; p > 1; p >>= 1)
  32.     segsL[i][p >> 1] = segsL[i][p] + segsL[i][p ^ 1];
  33. }
  34. // Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
  35. int queryL(int n, int i, int l, int r) { // sum on interval [l, r)
  36.   int res = 0;
  37.   for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  38.     if (l & 1) res += segsL[i][l++];
  39.     if (r & 1) res += segsL[i][--r];
  40.   }
  41.   return res;
  42. }
  43.  
  44. void precalc(int n, string & s) {
  45.   int i, j;
  46.   for (i = 0; i < n; i++) {
  47.     for (j = 0; j < n; j++) {
  48.       // [longest match left, longest match right]
  49.       m[i][j][0] = (s[i] == s[j]) & 1;
  50.       m[i][j][1] = (s[i] == s[j]) & 1;
  51.     }
  52.   }
  53.  
  54.   for (i = n - 2; i >= 0; i--)
  55.     for (j = n - 2; j >= 0; j--)
  56.       m[i][j][1] = s[i] == s[j] ? 1 + m[i + 1][j + 1][1] : 0;
  57.  
  58.   for (i = 1; i < n; i++)
  59.     for (j = 1; j < n; j++)
  60.       m[i][j][0] = s[i] == s[j] ? 1 + m[i - 1][j - 1][0] : 0;
  61. }
  62.  
  63. void f(int n, string & s) {
  64.   int i, j, k, longest;
  65.  
  66.   dp[0][n - 1] = 1;
  67.   update(n, n - 1, 1);
  68.   updateL(n, n - 1, 0, 1);
  69.  
  70.   // Right side initialisation
  71.   for (j = n - 2; j >= 0; j--) {
  72.     if (s[0] == s[j + 1]) {
  73.       longest = std::min(j + 1, m[0][j + 1][1]);
  74.       for (k = j + 1; k <= j + longest; k++)
  75.         dp[0][j] |= dp[0][k];
  76.       if (dp[0][j]) {
  77.         update(n, j, 1);
  78.         updateL(n, j, 0, 1);
  79.         best = std::min(best, j + 1);
  80.       }
  81.     }
  82.   }
  83.  
  84.   // Left side initialisation
  85.   for (i = 1; i < n; i++) {
  86.     if (s[i - 1] == s[n - 1]) {
  87.       // We are bound by the current range
  88.       longest = std::min(n - i, m[i - 1][n - 1][0]);
  89.       for (k = i - 1; k >= i - longest; k--)
  90.         dp[i][n - 1] |= dp[k][n - 1];
  91.       if (dp[i][n - 1]) {
  92.         updateL(n, n - 1, i, 1);
  93.         best = std::min(best, n - i);
  94.       }
  95.     }
  96.   }
  97.  
  98.   for (i = 1; i <= n - 2; i++) {
  99.     for (int ii = 0; ii < MAX_N; ii++) {
  100.       seg[ii * 2] = 0;
  101.       seg[ii * 2 + 1] = 0;
  102.     }
  103.     update(n, n - 1, dp[i][n - 1]);
  104.     for (j = n - 2; j >= i; j--) {
  105.       // We removed on the right
  106.       if (s[i] == s[j + 1]) {
  107.         // We are bound by half the current range
  108.         longest = std::min(j - i + 1, m[i][j + 1][1]);
  109.         //for (k=j+1; k<=j+longest; k++)
  110.         //dp[i][j] |= dp[i][k];
  111.         if (query(n, j + 1, j + longest + 1)) {
  112.           dp[i][j] = 1;
  113.           update(n, j, 1);
  114.           updateL(n, j, i, 1);
  115.         }
  116.       }
  117.       // We removed on the left
  118.       if (s[i - 1] == s[j]) {
  119.         // We are bound by half the current range
  120.         longest = std::min(j - i + 1, m[i - 1][j][0]);
  121.         //for (k=i-1; k>=i-longest; k--)
  122.         //dp[i][j] |= dp[k][j];
  123.         if (queryL(n, j, i - longest, i)) {
  124.           dp[i][j] = 1;
  125.           updateL(n, j, i, 1);
  126.           update(n, j, 1);
  127.         }
  128.       }
  129.       if (dp[i][j])
  130.         best = std::min(best, j - i + 1);
  131.     }
  132.   }
  133. }
  134.  
  135. int main() {
  136.   string s;
  137.   cin >> s;
  138.   int n = s.length();
  139.   best = n;
  140.   precalc(n, s);
  141.   f(n, s);
  142.  
  143.   cout << best;
  144. }
Success #stdin #stdout 3.91s 421080KB
comments (?)
stdin
copy 
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
stdout
copy 
1
https://ideone.com/EIrhnR
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!