Best Reward
题意：
将一段字符串 分割成两个串
如果分割后的串为回文串，则该串的价值为所有字符的权值之和（字符的权值可能为负数），否则为0。
问如何分割，使得两个串权值之和最大
题解：
将原串s1反转得到s2，然后进行s1,s2扩展KMP匹配,得到extend,对于s1的前i个字符如果和s2的后i个字符相等即extend[len-i] == i则前i个字符为回文串,同理，要判断后len-i个字符是否是回文串，对s2,s1进行扩展KMP即可
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=500010;
const int INF=0x7fffffff;
int nxt[MAXN],ex1[MAXN],ex2[MAXN];
char s1[MAXN],s2[MAXN];
int sum[MAXN],val[30];
void getNext(char *str,int *next)
{
int i=0,j,p0,len=strlen(str);
next[0]=len;
while(i+1<len&&str[i]==str[i+1]) i++;
next[1]=i;
p0=1;
for(i=2;i<len;i++)
{
if(i+next[i-p0]<next[p0]+p0) next[i]=next[i-p0];
else
{
j=next[p0]+p0-i;
if(j<0) j=0;
while(i+j<len&&str[i+j]==str[j]) j++;
next[i]=j;
p0=i;
}
}
}
void getExtend(char *str,char *p,int *next,int *extend)
{
int i=0,j,p0,slen=strlen(str),plen=strlen(p);
getNext(p,next);
while(i<slen&&i<plen&&str[i]==p[i]) i++;
extend[0]=i;
p0=0;
for(i=1;i<slen;i++)
{
if(next[i-p0]+i<extend[p0]+p0) extend[i]=next[i-p0];
else
{
j=extend[p0]+p0-i;
if(j<0) j=0;
while(i+j<slen&&j<plen&&str[i+j]==p[j]) j++;
extend[i]=j;
p0=i;
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
sum[0]=0;
for(int i=0;i<26;i++)
{
scanf("%d",val+i);
}
scanf("%s",s1);
int len=strlen(s1);
for(int i=1;i<=len;i++)
{
sum[i]=sum[i-1]+val[s1[i-1]-'a'];
}
for(int i=0,j=len-1;i<len;i++,j--)
{
s2[i]=s1[j];
}
s2[len]=0;
getExtend(s1,s2,nxt,ex1);
getExtend(s2,s1,nxt,ex2);
int ans=-INF,num;
for(int i=1;i<len;i++)
{
num=0;
if(ex1[i]==len-i) num+=sum[len]-sum[i];//表示后len-i个字符为回文串
if(ex2[len-i]==i) num+=sum[i];//表示前i个字符是回文串
if(num>ans) ans=num;
}
printf("%d\n",ans);
}
}
题意：
给一个数字字符串S， 可以把S最后一个数字移动到最前面变成另一个数字。例如123， 经过移动依次变成312，231，123。 注意当移动次数正好和S长度相等时，S又变回了最开始的那个数字。
求这个移动过程所形成的所有字符串，大于S（最初的）的数字，等于S，以及小于S的各有多少个。
题解：
因为比较数字大小主要是找第一个不同的的位的大小，所以我们可以利用扩展kmp。假设原串为s1,构造s2=s1+s1；然后s1作为模式串,对s1求next数组，s2求extend数组，那么extends[i]表示s2的第i个位置开始,与s1相同的字符的个数，所以要比较大小，只需比较s2[i+extend[i]]和s1[extend[i]]。需要注意的是,当extend[i]==strlen(s1)，说明这两数字是相等的，还有就是，题目求的是不重复的数字的个数，所以还要借助循环节。
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1e6;
char s1[MAXN],s2[MAXN];
int next[MAXN],extend[MAXN];
void getFail(char *str)
{
int len=strlen(str);
int j=0,k=-1;
next[0]=-1;
while(j<len)
{
if(k==-1||str[j]==str[k])
{
next[++j]=++k;
}
else k=next[k];
}
}
void getNext(char *str)
{
int len=strlen(str),i=0,j,p0;
while(i+1<len&&str[i+1]==str[i]) i++;
next[0]=len;
next[1]=i;
p0=1;
for(i=2;i<len;i++)
{
if(next[i-p0]+i<next[p0]+p0)
{
next[i]=next[i-p0];
}
else
{
j=next[p0]+p0-i;
if(j<0) j=0;
while(i+j<len&&str[i+j]==str[j]) j++;
next[i]=j;
p0=i;
}
}
}
void getExtend(char *str,char *p)
{
int i=0,j,p0,slen=strlen(str),plen=strlen(p);
getNext(p);
while(i<slen&&i<plen&&str[i]==p[i]) i++;
extend[0]=i;
p0=0;
for(i=1;i<slen;i++)
{
if(i+next[i-p0]<extend[p0]+p0) extend[i]=next[i-p0];
else
{
j=extend[p0]+p0-i;
if(j<0) j=0;
while(i+j<slen&&j<plen&&str[i+j]==p[j]) j++;
extend[i]=j;
p0=i;
}
}
}
int main()
{
int t,equ,les,big,slen;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{
scanf("%s",s1);
getFail(s1);
int len1=strlen(s1);
int num=len1-next[len1];
num=(len1%num==0)?len1/num:1;
equ=les=big=0;
for(int i=0;i<len1;i++)
{
s2[i]=s1[i];
s2[i+len1]=s1[i];
}
s2[len1+len1]=0;
getExtend(s2,s1);
for(int i=0;i<len1;i++)
{
if(extend[i]==len1) equ++;
else if(s2[i+extend[i]]>s1[extend[i]]) big++;
else les++;
}
printf("Case %d: %d %d %d\n",cas,les/num,equ/num,big/num);
}
}
