zoj4110 Strings in the Pocket（manacher）

谁借莪１个温暖的怀抱￠ 2021-12-17 06:05 192阅读 0赞

传送：[http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=6012][http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemId_6012]

题意：给定两个串$S$和$T$，可以翻转$S$串中的任意一个子段，得到$T$。问，可以翻转的方案书有多少？

数据范围：多组数据。$1\\leq|S|\\leq2\\times10^5$，$\\sum|S|\\leq2\\times10^7$。

分析：很明显需要分类讨论$S$与$T$比较的各种情况。

首先需要判断$S$串从左和从右找到与$T$开始不同的位置。

1.  $S$不可以翻转成$T$：就是指$S$串中不同的那一段不可以通过翻转得到$T$，方案数为0。
2.  $S$与$T$不同的“中间”那一段可以通过翻转得到对应$T$的那一段。这个时候需要向外扩展判断最长可以扩展到的位置。
3.  $S$与$T$完全相同，这个时候就需要通过manacher来求解整个串内回文子串的个数。

代码：

1.  不分奇偶讨论的manacher

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int maxn=2e6+10;
     5 char S[maxn],T[maxn],s[maxn*2];
     6 int p[maxn*2],len;
     7 int init(){
     8     s[0]=s[1]='#';
     9     for (int i=0;i<len;i++){
    10         s[i*2+2]=S[i];
    11         s[i*2+3]='#';
    12     } 
    13     len=len*2+2;
    14     s[len]=0;
    15 }
    16 void manacher(){
    17     int id,mx=0; 
    18     for (int i=1;i<len;i++){
    19         if(i<mx) p[i]=min(p[(id<<1)-i],p[id]+id-i);
    20         else p[i]=1;
    21         while (s[i-p[i]]==s[i+p[i]]) p[i]++;
    22         if (mx<i+p[i]){
    23             id=i;mx=i+p[i];
    24         }
    25     }
    26 }
    27 int main(){
    28     int t; scanf("%d",&t);
    29     while (t--){
    30         scanf("%s",S);
    31         scanf("%s",T);
    32         len=strlen(S);
    33         int l=0,r=len-1; ll ans=0;
    34         while (S[l]==T[l] && l<len) l++;
    35         while (S[r]==T[r] && r>=0) r--;
    36         if (l==r){printf("0\n"); continue;}
    37         if (l<len){
    38             ans=1;
    39             for (int i=l;i<=r;i++)
    40                 if (S[i]!=T[l+r-i]){
    41                     ans=0; break;
    42                 }
    43             if (ans){
    44                 ans=1;
    45                 l--;r++;
    46                 while (l>=0 && r<len && S[l]==T[r] && S[r]==T[l]){
    47                     l--;r++;ans++;
    48                 }
    49             }
    50             printf("%d\n",ans);
    51         }
    52         else{
    53             init();
    54             manacher(); ans=1;
    55             for (int i=0;i<len;i++) ans+=(p[i]/2);
    56             printf("%lld\n",ans-1);
    57         }
    58     }
    59     return 0;
    60 }

2.分奇偶讨论的manacher

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int maxn=2e6+10;
     5 char S[maxn],T[maxn];
     6 int odd[maxn],eve[maxn],len;
     7 ll manacher(){
     8     int l=-1,r=-1,x;
     9     ll ans=0;
    10     for(int i=0;i<len;i++)
    11     {
    12         if (i>r) x=1;
    13         else x=min(odd[l+r-i],r-i);
    14         while (i-x>=0 && i+x<len && S[i-x]==S[i+x]) x++;
    15         odd[i]=x;
    16         ans+=x;
    17         if (i+x-1>r) {r=i+x-1;l=i-x+1;}
    18     }
    19     l=r=-1;
    20     for(int i=0;i<len;i++)
    21     {
    22         if(i>r) x=0;
    23         else x=min(eve[l+r-i+1],r-i+1);
    24         while (i-x-1>=0 && i+x<len && S[i-x-1]==S[i+x]) x++;
    25         eve[i]=x;
    26         ans+=x;
    27         if (i+x>=r) {l=i-x;r=i+x-1;}
    28     }
    29     return ans;
    30 }
    31 int main(){
    32     int t; scanf("%d",&t);
    33     while (t--){
    34         scanf("%s",S);
    35         scanf("%s",T);
    36         len=strlen(S);
    37         int l=0,r=len-1; ll ans=0;
    38         while (S[l]==T[l] && l<len) l++;
    39         while (S[r]==T[r] && r>=0) r--;
    40         if (l==r){printf("0\n"); continue;}
    41         if (l<len){
    42             ans=1;
    43             for (int i=l;i<=r;i++)
    44                 if (S[i]!=T[l+r-i]){
    45                     ans=0; break;
    46                 }
    47             if (ans){
    48                 ans=1;
    49                 l--;r++;
    50                 while (l>=0 && r<len && S[l]==T[r] && S[r]==T[l]){
    51                     l--;r++;ans++;
    52                 }
    53             }
    54             printf("%d\n",ans);
    55         }
    56         else{
    57             ans=manacher();
    58             printf("%lld\n",ans);
    59         }
    60     }
    61     return 0;
    62 }

转载于:https://www.cnblogs.com/changer-qyz/p/10792437.html

[http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemId_6012]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=6012