http://acm.hdu.edu.cn/showproblem.php?pid=5340

The question

Determine whether the string can be S It is divided into three non empty palindromes

analysis

manacher Preprocess the position of prefix and suffix palindrome , Enumerates the first palindrome string and the third palindrome string , So we get the interval of the second palindrome string , Find the midpoint , because manacher After processing, all palindrome strings are odd in length , Then judge whether the middle part is palindrome or not according to the palindrome radius of the midpoint , Complexity o(n2). as for n2 Why can complexity pass .. Is not very good

#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#define rep(i,e) for(int i=0;i<(e);i++)
#define rep1(i,e) for(int i=1;i<=(e);i++)
#define repx(i,x,e) for(int i=(x);i<=(e);i++)
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define mset(var,val) memset(var,val,sizeof(var))
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define pd(a) printf("%d\n",a)
#define scl(a) scanf("%lld",&a)
#define scll(a,b) scanf("%lld%lld",&a,&b)
#define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define IOS ios::sync_with_stdio(false);cin.tie(0) using namespace std;
typedef long long ll;
template <class T>
void test(T a){cout<<a<<endl;}
template <class T,class T2>
void test(T a,T2 b){cout<<a<<" "<<b<<endl;}
template <class T,class T2,class T3>
void test(T a,T2 b,T3 c){cout<<a<<" "<<b<<" "<<c<<endl;}
const int N = 1e6+;
//const int MAXN = 210;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = ;
int T;
void testcase(){
printf("Case #%d: ",++T);
}
const int MAXN = 4e4+;
const int MAXM = ;
char ma[MAXN],s[MAXN];
int mp[MAXN];
int pre[MAXN],suf[MAXN];
void Manacher(int len){
int l=;
ma[l++]='$';
ma[l++]='#';
for(int i=;i<len;i++) ma[l++]=s[i],ma[l++]='#';
ma[l]=;
int mx=,id=;
for(int i=;i<l;i++){
mp[i]=mx>i?min(mp[*id-i],mx-i):;
while(ma[i+mp[i]]==ma[i-mp[i]]) mp[i]++;
if(i+mp[i]>mx){
mx=i+mp[i];
id=i;
}
}
}
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif // LOCAL
int t;
scd(t);
while(t--){
scanf("%s",s);
int len = strlen(s);
Manacher(len);
int l=,r=;
len=*len+;
for(int i=;i<=len;i++){
if(mp[i]==i&&i!=) pre[l++]=mp[i];
//mp[i]==i Guarantee mp[i] Can be used as the radius of the first palindrome string , Join in pre Array ,i!=1 Make sure that the first palindrome string is not empty
if(mp[i]+i-==len&&i!=len) suf[r++]=mp[i];
}
int i,j;
for(i=l-;i>=;i--){
for(j=;j<r;j++){
int t1=*pre[i];
int t2=len+-*suf[j];
int tmp = (t1+t2)>>;
if(t1>t2) continue;
if(mp[tmp]==) continue;
if(mp[tmp]*->=t2-t1+) break;
}
if(j<r) break;
}
if(i>=) puts("Yes");
else puts("No");
}
return ;
}

HDU - 5340 Three Palindromes(manacher Algorithm ) More articles about

  1. hdu 5340 Three Palindromes

    The other night BC The second question of , The official answer is : And then I combined it with what I saw yesterday Manacher The algorithm tried to write , Find out pre.suf Arrays are hard to construct , I've been debugging for a long time , Then we enumerate the middle , The complexity should be O(n2) ...

  2. hdu 3613&quot;Best Reward&quot;(Manacher Algorithm )

    Portal The question : The king rewarded the generals who had made great contributions to the war Li, Decide to award Li A necklace , This necklace contains 26 Middle bead "a~z", Every kind of bead has The corresponding value (-100~100), When a necklace can form palindrome ...

  3. HDU 5340——Three Palindromes——————【manacher Processing palindrome strings 】

    Three Palindromes Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others ...

  4. HDU 5340 Three Palindromes (Manacher)

    The question : Determine whether the string can be S It is divided into three non empty palindromes . Ideas : First preprocess the positions of prefix palindrome string and suffix palindrome string , Load positions into two separate sets ,O(n). For the end position of each prefix palindrome string , Pick out disjoint suffix palindrome strings , Yes, the middle one ...

  5. Manacher Algorithm (hdu 3068 &amp;&amp; hdu 3294)

    I'm going to make up for the night before yesterday BC The second question of , It's found to be useful in O(n) Time to find the length of the largest palindrome substring  Manacher Algorithm , Listen to for the first time , So I went to Baidu , I watched it for a long time , Finally, I can understand his thought , As for the code template he gave me, I didn't see it completely ...

  6. hdu 3068 The longest palindrome manacher Algorithm ( video )

    Sentiment : First of all, I want to Orz once qsc, It's hard for me to find information about acm Teaching video of , But I came across this , I feel like I did a good job , link : To poke I feel that this kind of people who spend their time teaching others is really great . manacher The algorithm changes all palindromes ...

  7. hdu5340—Three Palindromes—(Manacher Algorithm )—— Palindrome string

    Three Palindromes Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others ...

  8. HDU 5371(2015 Multi school 7)-Hotaru&amp;#39;s problem(Manacher Algorithm for palindrome string )

    Title address :HDU 5371 The question : Give you an example with n An integer sequence of elements , Ask if you have such a subsequence . The subsequence is divided into three parts , The first part is the same as the third part , The first part is symmetrical to the second part . Suppose there is a longest sequence that satisfies this condition . ...

  9. HDU 3068: The longest palindrome (Manacher Algorithm )

    http://acm.hdu.edu.cn/showproblem.php?pid=3068 The longest palindrome Problem Description   Give a small English character a,b,c...y,z Composed of ...

Random recommendation

  1. see SQL SERVER Database operation parameters and connection number

    --- View all requests of the current database system . I just list the fields that I think are more important to help me solve the problem . SELECT ds.session_id, ds.status, Db_name(dr.database_id) ...

  2. Use python + tornado Do the project demo Demo template

    It's simple , But it's not time , A lot of detours . Note here , For future needs . # web_server.py #!/usr/bin/env python # coding=utf-8 import os ...

  3. JavaPersistenceWithHibernate Second edition notes - The fifth chapter -Mapping value types-007UserTypes Usage of (@org.hibernate.annotations.Type、@org.hibernate.annotations.TypeDefs、CompositeUserType、DynamicParameterizedType、、、)

    One . structure Two .Hibernate Supported by UserTypes Interface  UserType —You can transform values by interacting with the plain JD ...

  4. java.net.BindException: Not enough permissions

    stay Linux Next , Today I wrote a socket Applet , binding 80 port , It's abnormal The reason is that linux Next , If you use 1024 The following ports require root jurisdiction , So because I'm not using root jurisdiction , So authority ...

  5. C++ When an array is a function parameter , Passing the size of an array

    I don't say much nonsense , Let's start with the error demonstration : void fun(int arr[arr_num]) { // ... } int main() { // ... int *arr = new int[10]; fun( ...

  6. SQL Server Of 3 A connection

    The first one is 1. nested loop: select * from tableA inner join tableB on tableA.X = tableB.X; Its execution process is like this . about tabl ...

  7. glusterfs 4.0.1 rpc Analysis notes 2 (socket.so modular )

    socket.c stay 4000 The row position defines a set of structural functions , We can start here and find the entrance , If it's a client, you need to call connect, If it is a server, it needs to call listen, struct rpc_transport_ ...

  8. Oracle Service Bus white paper

    Oracle Service Bus brief introduction In the face of changing market demand , Companies want to promote " As a service " Improve agility and responsiveness : More easily interact with customers and partners , Design and build more flexibly IT Infrastructure ...

  9. Domain build OU Organizational unit

    Start with this interface : stay baidu.com Right click --- newly build ---- Organizational unit ---- Beijing Branch stay baidu.com Right click --- newly build ---- Organizational unit ---- Beijing Branch In Beijing Branch And Nanjing Branch ...

  10. css3 box-flex

    App address :http://www.jb51.net/css/467291.html box-flex yes css3 Newly added box model properties , It breaks the floating layout that we often use , Achieve vertical contour . Level average . Scale ...