首页 > 其他 > 详细

LOJ6387 [THUPC2018] 绿绿与串串 【manacher】

时间:2018-05-22 00:24:36      阅读:243      评论:0      收藏:0      [点我收藏+]

题目分析:

比较简单,先跑一边manacher,然后对于回文部分可以碰到末尾的一定满足条件,否则向后转移。

代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 1000020;
 5 
 6 char str[maxn],solve[maxn<<1];
 7 int f[maxn<<1],n;
 8 
 9 void manacher(){
10     memset(f,0,sizeof(f));
11     for(int i=2*n-2,j=n-1;i>=2;i-=2,j--){
12     solve[i] = str[j];solve[i-1] = $;
13     }
14     solve[0] = str[0];
15     f[0] = 1; n = 2*n-1;
16     int fr = 0,last = 0;
17     for(int i=1;i<n;i++){
18     if(last + fr >= i){
19         if(last-(i-last)-f[last-(i-last)]+1 >= last- fr)f[i]=min(n-i,f[last-(i-last)]);
20         else f[i] = min(n-i,last+fr-i+1);
21         while(i-f[i]>=0&&f[i]+i<n&&solve[f[i]+i]==solve[i-f[i]])
22         f[i]++;
23         if(i+f[i]-1 >= last+fr) last = i,fr = f[i]-1;
24     }else{
25         f[i] = 1;
26         while(i-f[i]>=0&&f[i]+i<n&&solve[f[i]+i]==solve[i-f[i]]) f[i]++;
27         last = i; fr = f[i]-1;
28     }
29     }
30 }
31 
32 int ans[maxn];
33 void work(){
34     memset(ans,0,sizeof(ans));
35     n = strlen(str);int trans = n;
36     manacher(); n = trans;
37     for(int i=n-1;i>=0;i--){
38     int len =  (f[i*2]+1)/2;
39     if(i + len == n) {ans[i] = 1;continue;}
40     if(i - len + 1 == 0){ans[i] = ans[i+len-1];continue;}
41     }
42     for(int i=0;i<n;i++) if(ans[i]) printf("%d ",i+1);
43     puts("");
44 }
45 
46 int main(){
47     int t; scanf("%d",&t);
48     while(t--){
49     scanf("%s",str);
50     work();
51     }
52     return 0;
53 }

 

LOJ6387 [THUPC2018] 绿绿与串串 【manacher】

原文:https://www.cnblogs.com/Menhera/p/9070014.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!