相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4650
神犇题解：https://blog.sengxian.com/solutions/bzoj-4650
解题报告
主要是统计以每个点为开头/结尾的能划分成两个相等子串的串有多少个
这个是SA的经典应用
当然问能划分成x个相同子串的问题，SA也是一样的做法
比如：https://www.codechef.com/problems/TANDEM
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 60009;
const int SGZ = 26;
const int M = 15;
char pat[N];
int n,c1[N],c2[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
class Suffix_Array{
char s[N]; int *rak,*que,len,dif;
int arr1[N],arr2[N],bot[N],sa[N],height[N];
class Sparse_Table{
int mn[N][M],len;
public:
inline void init(int LEN, int *height) {
len = LEN; memset(mn,0,sizeof(mn));
for (int i=1;i<=len;i++) mn[i][0] = height[i];
for (int j=1,w=1;j<M;j++,w<<=1) {
for (int i=1,l=len-w;i<=l;i++) {
mn[i][j] = min(mn[i][j-1], mn[i+w][j-1]);
}
}
}
inline int query(int l, int r) {
if (l > r) swap(l, r); ++l;
int h = r - l + 1 >> 1, t = 0, L = 1;
while (L <= h) L<<=1, t++;
return min(mn[l][t],mn[r-L+1][t]);
}
}st;
public:
inline void init(char *S, int L) {
memset(s,0,sizeof(s));
memset(arr1,0,sizeof(arr1));
memset(arr2,0,sizeof(arr2));
for (int i=1;i<=L;i++) s[i] = S[i];
len = L; build();
}
inline int query(int l, int r) {
if (l < 0 || l > len || r < 0 || r > len) return 0;
else return st.query(rak[l], rak[r]);
}
inline void out() {
cout<<"----------"<<endl;
for (int i=1;i<=len;i++) printf("%d ",sa[i]); cout<<endl;
for (int i=1;i<=len;i++) printf("%d ",height[i]); cout<<endl;
cout<<"----------"<<endl;
}
private:
inline void build() {
rak = arr1; que = arr2;
for (int i=1;i<=SGZ;i++) bot[i] = 0;
for (int i=1;i<=len;i++) bot[s[i]-'a'+1]++;
for (int i=2;i<=SGZ;i++) bot[i] += bot[i-1];
for (int i=1;i<=len;i++) sa[bot[s[i]-'a'+1]--] = i;
rak[sa[1]] = dif = 1;
for (int i=2;i<=len;i++) rak[sa[i]] = (dif += (s[sa[i]]!=s[sa[i-1]]));
for (int l=1,tot;tot=0,l<=len;l<<=1) {
for (int i=len-l+1;i<=len;i++) que[++tot] = i;
for (int i=1;i<=len;i++) if (sa[i] > l) que[++tot] = sa[i] - l;
for (int i=1;i<=dif;i++) bot[i] = 0;
for (int i=1;i<=len;i++) bot[rak[i]]++;
for (int i=2;i<=dif;i++) bot[i] += bot[i-1];
for (int i=len;i;i--) sa[bot[rak[que[i]]]--] = que[i];
swap(que, rak); rak[sa[1]] = dif = 1;
for (int i=2;i<=len;i++)
if (que[sa[i]]==que[sa[i-1]]&&que[sa[i]+l]==que[sa[i-1]+l]) rak[sa[i]]=dif;
else rak[sa[i]] = ++dif;
if (dif >= len) break;
}
for (int i=1;i<=len;i++) {
int t = max(0, height[rak[i-1]] - 1);
int p1 = i + t, p2 = sa[rak[i]-1] + t;
for (;s[p1]==s[p2];p1++,p2++) ++t;
height[rak[i]] = t;
}
st.init(len, height);
}
}dir,rev;
int main() {
for (LL T=read(),vout;vout=0,T;T--) {
memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2));
scanf("%s",pat+1); n = strlen(pat+1);
dir.init(pat, n);
for (int i=1,j=n;i<j;i++,j--) swap(pat[i], pat[j]);
rev.init(pat, n);
for (int l=1,suf,pre,L,R;l<=n;l++) {
for (int i=1;i<=n;i+=l) {
suf = dir.query(i, i+l);
pre = rev.query(n-i+2, n-i-l+2) + 1;
L = max(i, i + l - pre);
R = min(i + l - 1, i + suf - 1);
if (L <= R) {
c1[L+l]++; c1[R+l+1]--;
c2[L-l]++; c2[R-l+1]--;
}
}
}
for (int i=1,t1=c1[0],t2=c2[0];i<=n;i++) {
t1 += c1[i]; t2 += c2[i];
vout += (LL)t1 * t2;
}
printf("%lld\n",vout);
}
return 0;
}
Great delivery. Sound arguments. Keep up the great effort.
I was very happy to discover this web site. I want to to
thank you for your time just for this wonderful read!!
I definitely loved every part of it and i also have you book marked to see new information on your site.
Remarkable things here. I am very happy to peer your post.
Thank you a lot and I’m taking a look forward to touch you.
Will you kindly drop me a e-mail?
My family always say that I am killing my time here at
web, however I know I am getting experience all the time by
reading such nice posts.
Ridiculous story there. What happened after? Thanks!
What a data of un-ambiguity and preserveness of valuable familiarity
on the topic of unexpected emotions.
When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time
a comment is added I get three emails with the same comment.
Is there any way you can remove people from that service?
Bless you!
hello!,I really like your writing very much! share we communicate
extra about your article on AOL? I need an expert on this
house to resolve my problem. Maybe that is you! Taking a
look ahead to look you.
Thanks for sharing your thoughts about ps4 games. Regards
Hey! I’m at work surfing around your blog from my new iphone!
Just wanted to say I love reading through your blog and look forward to all your posts!
Keep up the excellent work!
naturally like your web site but you have to check the spelling on several of your posts. Many of them are rife with spelling problems and I find it very bothersome to tell the truth nevertheless I will definitely come back again.
Hello there! This is my first visit to your blog! We are a collection of
volunteers and starting a new project in a community in the same
niche. Your blog provided us beneficial information to work on. You have
done a marvellous job!
When I initially left a comment I appear to have clicked on the -Notify me when new comments are added- checkbox and from
now on whenever a comment is added I receive 4 emails
with the exact same comment. Perhaps there is a way you can remove
me from that service? Thank you!
Awesome! Its really amazing piece of writing, I have got much clear idea about from
this post.
I really like your blog.. very nice colors & theme.
Did you make this website yourself or did you hire someone to do it for you?
Plz reply as I’m looking to create my own blog and would like to find out where u got this from.
many thanks
you are actually a just right webmaster. The website loading speed is
incredible. It kind of feels that you are doing any unique trick.
Furthermore, The contents are masterpiece. you have performed a great task on this topic!
Have you ever considered creating an ebook or guest authoring
on other websites? I have a blog centered on the same subjects you discuss and would
love to have you share some stories/information. I know my
audience would appreciate your work. If you’re even remotely interested, feel free
to shoot me an e mail.
Magnificent goods from you, man. I’ve understand your stuff previous to and you are just too fantastic.
I really like what you have acquired here, really like
what you’re saying and the way in which you say it.
You make it entertaining and you still care for to keep it wise.
I cant wait to read far more from you. This is actually
a great site.
It is appropriate time to make some plans for the future and it is time to be happy. I’ve read this post and if I could I want to suggest you some interesting things or suggestions. Perhaps you could write next articles referring to this article. I wish to read more things about it!