题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3790
离线版题目：http://paste.ubuntu.com/17470379/
吐槽：板题，直接上代码不解释
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 120000;
char pat[MAXN],chr[MAXN];
int n,l[MAXN],r[MAXN],len[MAXN],ord[MAXN];
namespace FenwickTree{
#define BIT FenwickTree
#define low(x) (x&(-x))
#define INF 1000000000
int arr[MAXN],buf[MAXN];
inline void init(){
for (int i=1;i<=n;i++)
arr[i] = buf[i] = INF;
}
inline int query(int left, int right){
if (right < left) return INF; else { int ret = INF; while (right >= left){
if (right-low(right)+1>=left) ret = min(ret,arr[right]),right-=low(right);
else ret = min(ret,buf[right]), right--;
}
return ret;
}
}
inline void modify(int pos, int nv){
if (buf[pos] > nv) {
buf[pos] = nv;
for (int i=pos;i<=n;i+=low(i)) if (arr[i] > nv) arr[i] = nv;
else break;
} else return;
}
};
inline bool sort_cmp(const int &A, const int &B){
return r[A] < r[B];
}
inline int manacher(){
int m=n*2+1,itr=0;
for (int i=1;i<=n;i++)
chr[i*2-1] = '@',
chr[i*2] = pat[i];
chr[m] = '@'; chr[m+1] = '#'; chr[0] = '$';
for (int i=1,p1,p2;i<=m;i++){ if (itr+len[itr] > i) len[i] = min(len[2*itr-i],itr+len[itr]-i);
else len[i] = 0;
p1 = i-len[i]; p2 = i+len[i];
while (chr[--p1] == chr[++p2]) len[i]++;
if (itr+len[itr] < i+len[i]) itr = i;
}
for (int i=1;i<=m;i++)
r[i] = i+len[i],
l[i] = i-len[i],
ord[i] = i;
sort(ord+1,ord+m,sort_cmp);
n = m; BIT::init(); BIT::modify(1,0);
for (int j=1,i=ord[j],tmp;j<=n;j++,i=ord[j]){
tmp = BIT::query(l[i],r[i]-1)+1;
BIT::modify(r[i],tmp);
}
return BIT::query(m-1,m)-1;
}
int main(){
while (~scanf("%s",pat+1)){
n = strlen(pat+1);
printf("%dn",manacher());
}
return 0;
}
Incredible points. Solid arguments. Keep up the
good effort.
Right away I am going away to do my breakfast, when having
my breakfast coming over again to read additional news.
What’s up, all the time i used to check webpage posts here early in the
morning, because i love to find out more and more.
I was able to find good info from your blog posts.
It’s very effortless to find out any matter
on net as compared to textbooks, as I found this post at this web
page.
It’s remarkable to pay a quick visit this website and reading the views of all colleagues on the topic
of this post, while I am also zealous of getting familiarity.
Thanks for one’s marvelous posting! I definitely enjoyed reading it, you are a great author.
I will be sure to bookmark your blog and may come back
very soon. I want to encourage you continue your great posts, have a
nice day!
Very rapidly this site will be famous amid all blog users, due
to it’s nice articles
First of all I want to say superb blog! I had
a quick question that I’d like to ask if you don’t mind.
I was curious to find out how you center yourself and clear your thoughts before writing.
I have had a hard time clearing my thoughts in getting my thoughts out there.
I truly do take pleasure in writing however it just seems like the first 10 to 15
minutes are generally lost simply just trying
to figure out how to begin. Any recommendations or hints?
Thanks!
You could certainly see your expertise in the work you write.
The sector hopes for more passionate writers like you who are not afraid to say how they believe.
At all times follow your heart.
Simply wish to say your article is as astounding.
The clarity to your put up is simply cool and that i could assume you’re an expert on this
subject. Well with your permission let me to snatch your feed to keep up to date with forthcoming post.
Thank you a million and please carry on the gratifying work.
Why visitors still use to read news papers when in this technological world the whole thing
is available on net?
Do you have a spam problem on this website; I also
am a blogger, and I was curious about your situation; we have developed some nice methods and we are looking to trade
strategies with other folks, why not shoot me an email if interested.
I have read a few just right stuff here. Definitely worth bookmarking for revisiting.
I wonder how a lot effort you put to make such a excellent informative website.
Hello. fantastic job. I did not expect this. This is a impressive story. Thanks!
Hello, after reading this awesome piece of writing i am as well happy to share my know-how
here with friends.
excellent put up, very informative. I ponder why the opposite specialists of
this sector do not notice this. You must proceed your writing.
I’m sure, you have a great readers’ base already!
This site really has all of the information I needed about this
subject and didn’t know who to ask.
Wonderful article! This is the kind of info that should be shared
around the net. Shame on Google for now not positioning this publish higher!
Come on over and discuss with my web site
. Thanks =)
Great blog here! Additionally your site so much up fast! What web host are you the use of? Can I am getting your associate hyperlink in your host? I wish my site loaded up as quickly as yours lol