扩展KMP( 一 )

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);
    }
}