密码最大KMP hdu4300 Clairewd’s message

本文笔者在广东吃饭的时候突然想到的...近期就有想写几篇关于密码最大的笔记，所以回家到之后就奋笔疾书的写出来发表了

题目链接：

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

题目意思：

给一个26个字母a-z对应的密码，给一个字符串，后面为密码后面为密码，让你找出最短的完整的信息，使后面一段时密码，后面一段时密码，而且不能重叠，中间不能有多的。如果不能找到，自己构造出一个。

解题思绪：

next[i]表示前缀密码和后缀密码最大的匹配长度。

注意最后next[n]可能大于n/2此时中间有重叠的地方，须要不断地往前移。

处理一下，一遍就可以搞定。

代码：

每日一道理
只有启程，才会到达理想和目的地，只有拼搏，才会获得辉煌的成功，只有播种，才会有收获。只有追求，才会品味堂堂正正的人。

#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 110000

char save[Maxn],change[27];
int next[Maxn],n;
char ss[27];

void getnext()
{
   int j=0;

   next[1]=0;
   for(int i=2;i<=n;i++)
   {
      while(j>0&&save[j+1]-change[save[i]-'a'])
         j=next[j];
      if(save[j+1]==change[save[i]-'a'])
         j++;
      next[i]=j;
   }
   //printf("%d\n",next[n]);
   if(next[n]<n/2)
      return ;
   int temp=n;
   while(next[n]>n/2) //大于一半，一直往前移
   {
      temp=next[temp];
      next[n]=temp;
   } //如果恰好有一半，就不必管了，这是最大的
   if(next[n]<n/2) //看是否再凑成一个
   {
      if(save[next[n]+1]==change[save[n]-'a'])
         next[n]++;
   }
   return ;
}

int main()
{
   int t;

   scanf("%d",&t);
   while(t--)
   {
      scanf("%s%s",change,save+1);
      for(int i=0;i<26;i++)
         ss[change[i]-'a']=i+'a';
      n=strlen(save+1);
      getnext();

     // printf("next:%d\n",next[n]);
      if(n-next[n]==next[n])
         printf("%s\n",save+1);
      else
      {
         printf("%s",save+1);
         for(int i=next[n]+1;i<=n-next[n];i++)
            putchar(ss[save[i]-'a']);
         putchar('\n');

      }
      //printf("%d\n",n);
   }
   return 0;
}

文章结束给大家分享下程序员的一些笑话语录：这年头的互联网真是娱乐了中国，网民们从各种各样的“门”里钻来钻去，又有好多“哥”好多“帝”，值得大家品味不已……网络经典语录，关于IT与互联网，经典与您分享！

--------------------------------- 原创文章 By 密码和最大 ---------------------------------