串字符串KMP hdu3613Best Reward

这段时间朋友几篇文章介绍了改串字符串的文章. 关联文章的地址

题目链接：

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

题目意思：

a-z每一个字母有一个值，给个字符串，让你分成两部分，每一部分至少有一个字符。

如果该串是回文字符串，则该值为全部字符的值之和，如果不是字符串，则为0.

让你计算怎样分割使得两部分的总和值最大。

解题思绪：

利用回文字符串的next[i]也是回文字符串的特点，求出串中全部的回文串。

然后倒过来，求出后缀的会问字符串。

然后一次遍历就可以求出最大的值。

代码：

每日一道理
这浓浓的母爱使我深深地认识到：即使你是一只矫健的雄鹰，也永远飞不出母爱的长空；即使你是一条扬帆行驶的快船，也永远驶不出母爱的长河！在人生的路上不管我们已走过多远，还要走多远，我们都要经过母亲精心营造的那座桥！

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF (1<<30)
#define PI acos(-1.0)
using namespace std;

#define Maxn 510000

int value[27],sum[2][Maxn]; //分离表示早年至后的回文串的值和从后到前的回文串的值
int ss[2][Maxn],next[Maxn*2]; //早年以后求出各值
char save[Maxn];
char stemp[Maxn*2];

void getnext(char * a,int len)
{
   int j=0;

   next[1]=0;
   for(int i=2;i<=len;i++)
   {
      while(j>0&&a[j+1]-a[i])
         j=next[j];
      if(a[j+1]==a[i])
         j++;
      next[i]=j;
   }
   return ;
}

int main()
{
   int t;

   scanf("%d",&t);
   while(t--)
   {
      for(int i=1;i<=26;i++)
         scanf("%d",&value[i]);
      scanf("%s",save+1);
      int len=strlen(save+1);
      memset(ss,0,sizeof(ss));
      for(int i=1;i<=len;i++) //预处理出全部的前缀值的和
         ss[0][i]=ss[0][i-1]+value[save[i]-'a'+1];
      for(int i=len;i>=1;i--) //预处理出全部的后缀值的和
         ss[1][len-i+1]=ss[1][len-i]+value[save[i]-'a'+1];

      strcpy(stemp+1,save+1);
      stemp[len+1]='*';
      strcpy(stemp+len+2,save+1);
     // printf("%s\n",stemp+1);
      std::reverse(stemp+len+2,stemp+len+len+2); //翻转
      //printf("%s\n",stemp+1);
      getnext(stemp,len+len+1);
      memset(sum,0,sizeof(sum));
      int i=len+len+1;
      do //是回文串，注意只有一个元素也是回文串
      {
         i=next[i];
        // printf("i:%d next[i]:%d\n",i,next[i]);
         sum[0][i]=ss[0][i];

      }while(next[i]);

      //倒过来再求一遍
      //printf("sum[0][1]:%d\n",sum[0][1]);
      std::reverse(stemp+1,stemp+len+1);
      std::reverse(stemp+len+2,stemp+len+len+2);
      getnext(stemp,len+len+1);
      i=len+len+1;
      do
      {
         i=next[i];
         sum[1][i]=ss[1][i];
      }while(next[i]);
      int ans=-INF;
      for(int i=1;i<len;i++)
         ans=max(ans,sum[0][i]+sum[1][len-i]);
      printf("%d\n",ans);
   }
   return 0;
}

文章结束给大家分享下程序员的一些笑话语录：自行车
一个程序员骑着一个很漂亮的自行车到了公司，另一个程序员看到了他，问到，“你是从哪搞到的这么漂亮的车的？”
骑车的那个程序员说， “我刚从那边过来，有一个漂亮的姑娘骑着这个车过来，并停在我跟前，把衣服全脱了，然后对我说，‘你想要什么都可以’”。
另一个程序员马上说到， “你绝对做了一个正确的选择，因为那姑娘的衣服你并不一定穿得了”。

--------------------------------- 原创文章 By
串和字符串
---------------------------------