前几晚 BC 的第二题，官方给出的题解是：

　　然后我结合昨天刚看的 Manacher 算法试着写了下，发现 pre、suf 数组挺难构造的，调试了好久，然后就对中间进行枚举了，复杂度应该是 O(n2) 吧，我第一次交时超时了，以为真的要用什么暴力压位，可是我还不会啊，然后作了一些少许的优化提交本想再 T 一次的，没想到竟然神奇的过了，900+ms 水过，原来还是能卡过的……于是我把更多的细节进行优化，把 *2 和 /2 操作都改为移位运算，再提交时就下降到了 700+ms  :-D

　　代码如下：

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N = 20003; 6  7 char s[N], s2[N << 1]; 8 int p[N << 1]; 9 bool pre[N], suf[N];10 11 int main() {12     int t;13     scanf("%d",&t);14     while(t--) {15         scanf("%s",s);16         int n = strlen(s);17         s2[0] = '$';18         s2[1] = '#';19         for(int i = 0; i < n; ++i) {20             s2[(i << 1) + 2] = s[i];21             s2[(i << 1) + 3] = '#';22         }23         n = (n << 1) + 2;24         s2[n] = '\0';25         int right = 0, id = 0;26         p[0] = 0;27         for(int i = 1; i < n; ++i) {28             if(right > i)29                 p[i] = min(p[(id << 1) - i], right - i);30             else    p[i] = 0;31             while(s2[i + p[i] + 1] == s2[i - p[i] - 1])    ++p[i];32             if(i + p[i] > right) {33                 right = i + p[i];34                 id = i;35             }36         }37 38         int slen = (n >> 1) - 1;39 40         for(int i = 0; i < slen; ++i) {41             int s2id = i + 2;42             pre[i] = (s2id - p[s2id] == 1);43         }44         for(int i = slen - 1; i >= 0; --i) {45             int s2id = i + slen + 1;46             suf[i] = (s2id + p[s2id] == n - 1);47         }48 49         bool flag = 0;50         for(int i = 4; i <= n - 4; ++i) {51             int j = s2[i] == '#' ? 2 : 1;52             for(; j <= p[i]; j += 2) {53                 int id1 = i - j - 1;54                 int id2 = i + j + 1;55                 if(pre[(id1 >> 1) - 1] && suf[(id2 >> 1) - 1]) {56                     flag = 1;57                     break;58                 }59             }60             if(flag)    break;61         }62         puts(flag ? "Yes": "No");63     }64     return 0;65 }