Sample Input

2 abc abaadada

 

 

Sample Output

Yes No

 

 

判断是否能成为3个非空回文子串

manacher算法求出个点回文长度，在找出第一个和最后一个保存下来，再判断中间的

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;typedef unsigned long long ull;#define MOD 3221225473#define MAXN 20005#define MIN 0#define MAX 1000001int n;char d[MAXN];char st[MAXN*2];int p[MAXN*2],begi[MAXN*2],tail[MAXN*2];int len;void manacher(){    int MaxId=0,id;    for(int i=0; i
          
           i) p[i]=min(p[2*id-i],MaxId-i); else p[i]=1; while(st[i+p[i]]==st[i-p[i]]) p[i]++; if(p[i]+i>MaxId) { id=i; MaxId=p[i]+i; } p[i] -= 1; }}int main(){ int T; scanf("%d",&T); while(T--) { getchar(); scanf("%s",d); int l = strlen(d); len = 0; st[len++] = '#'; for(int i = 0; i < l; i++) { st[len++] = d[i]; st[len++] = '#'; } st[len] = 0; manacher(); int flag = 0; int pn =0 ,ln = 0; for(int i = 1; i < len - 1; i++) { if(i - p[i] == 0) begi[pn++] = i; if(i + p[i] == len-1) tail[ln++] = i; } for(int i = 0; i < pn; i++) { for(int j = ln - 1; j>=0; j--) { int s1 = begi[i] + p[begi[i]]+1 ,s2 = tail[j] - p[tail[j]]-1; if(s1 > s2) break; int mid = (s1 + s2)/2; if(p[mid] >= mid-s1) { flag = 1; break; } } if(flag ) break; } if(flag ) printf("Yes\n"); else printf("No\n"); } return 0;}