【2019浙江省赛 - J】K Strings in the Pocket（MANACHER）

蔚落 2021-09-19 04:10 255阅读 0赞

题意：  
给字符串S和T，要求使S变为T  
操作：对S的区间（l，r）反转，方法数

两个字符串相等的情况，MANACHER求回文子串的个数  
不相等的话，找到s和t不相同的位置l，r，然后判断反转后能不能相等，不相等就不能翻转，相等的话，就往两边拓展答案。

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    
    
    struct MANACHER{ 
    #define STRSIZE 2010000
      char str[STRSIZE*2+5];
      int  radius[STRSIZE*2+5];
      int  str_len;
      MANACHER(){ }
      MANACHER(char *tar){ solver(tar);}
      int solver(char *tar);                //执行MANACHER算法
      int getMaxPalSize();                  //最长回文串长度
      long long getPalNum();                //不同回文串个数
    };
    int MANACHER::solver(char *tar){ 
        //(1)construct new string
        int tar_len=strlen(tar);
        str_len=tar_len*2+2;
        str[0]='~';
        str[1]='!';
        for (int i=0;i<tar_len;i++){ 
          str[i*2+2]=tar[i];
          str[i*2+3]='!';
        }
        str[str_len]=0;
        //(2)calculate radius
        int max_idx=-1;
        int center=-1;
        for (int i=0;i<str_len;i++){ 
          radius[i]=1;
          if (max_idx>i)
            radius[i]=min(max_idx-i+1,radius[center*2-i]);
          while(str[i+radius[i]]==str[i-radius[i]]) radius[i]++;
          //update max_idx
          if (max_idx<i+radius[i]-1){ 
            max_idx=i+radius[i]-1;
            center=i;
          }
        }
        return 0;
    }
    int MANACHER::getMaxPalSize(){ 
        int ans=0;
        for (int i=1;i<str_len;i++)
           ans=max(ans,radius[i]-1);
        return ans;
    }
    long long MANACHER::getPalNum(){ 
        long long ans=0;
        for (int i=1;i<str_len;i++){ 
          ans+=radius[i]/2;
        }
        return ans;
    }
    MANACHER x;
    const int maxn = 2e6+100;
    
    int T;
    char str1[maxn],str2[maxn];
    int main(int argc, char const *argv[])
    { 
    	// ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    	scanf("%d",&T);
    	while(T--)
    	{ 
    		// cin >> str1 >> str2;
    		scanf("%s%s",str1,str2);
    		if(strcmp(str1,str2) == 0)
    		{ 
    			x.solver(str1);
    			 printf("%lld\n",x.getPalNum());
    		}
    		else 
    		{ 
    			ll ans = 0;
    			int le = strlen(str1);
    			int l = 0;
    			int r = 0;
    			rep(i,0,le)
    			{ 
    				if(str1[i] != str2[i])
    				{ 
    					l = i;
    					break;
    				}
    			}
    			per(i,0,le)
    			{ 
    				if(str1[i] != str2[i])
    				{ 
    					r = i;
    					break;
    				}
    			}
    			int j = r;
    			int f = 0;
    			rep(i,l,r+1)
    			{ 
    				if(str1[i] != str2[j])
    				{ 
    					f = 1;
    					break;
    				}
    				j--;
    			}
    			if(f)
    			{ 
    				printf("0\n");
    			}
    			else
    			{ 
    				ans = 1;
    				while(l-1 >= 0 && r+1 < le &&str1[l-1] == str2[r+1])
    				{ 
    					ans++;
    					l--;
    					r++;
    				}
    				printf("%lld\n",ans);
    			}
    		}
    	}
    	return 0;
    }