P5446

P5446

• 由翻转可知：\(S[j, k] == S[k, i]\)

• 因此 R 是 S 的前缀 且 R 的后缀是回文串

  • 用 Manacher 算出最大回文半径 d

• 此外，R 也可以由多次反转得到

  • 条件是：
    • R' 经过反转后是符合R 是 S 的前缀 且 R 的后缀是回文串 的
    • 且 R' 本身是回文串，这使得 R' 翻转后得到 R

  # include <bits/stdc++.h>
  # define int long long
  using namespace std;
  const int N = (int)1e6 + 10;
  
  int t;
  int l, r, d[N];
  bool vis[N];
  char s[N];
  
  void Manacher(int n){
  	int l = 0, r = 0;
  	s[0] = '@', s[n + 1] = '#';	
  	for(int i = 1; i <= n; i++){
  		d[i] = 0;
  		if(i > r){
  			while(s[i + d[i]] == s[i - d[i]]){
  				d[i]++;
  			}
  			l = i - d[i] + 1;
  			r = i + d[i] - 1;
  		}else{
  			int j = l + (r - i);
  			if(j - d[j] >= l){
  				d[i] = d[j];
  			}else{
  				d[i] = r - i;
  				while(s[i + d[i]] == s[i - d[i]]){
  					d[i]++;
  				}				
  				l = i - d[i] + 1;
  				r = i + d[i] - 1;				
  			}
  		}
  	}
  	for(int i = 1; i <= n; i++){
  		d[i]--;
  	}
  }
  
  signed main(){
  //	freopen("1.in", "r", stdin);
  	cin >> t;
  	while(t--){
  		cin >> (s + 1);
  		
  		int n = strlen(s + 1);	
  		Manacher(n);
  		
  		for(int i = n; i >= 1; i--){
  			if(i + d[i] == n){
  				vis[i] = 1;
  			}else if(vis[i + d[i]] == 1 && i - d[i] == 1){
  				vis[i] = 1;
  			}
  		}
  		for(int i = 1; i <= n; i++){
  			if(vis[i] == 1){
  				cout << i << " ";
  			}
  			vis[i] = 0;
  		}
  		cout << "\n";
  	}
  }