J - Clairewd’s message HDU - 4300（扩展kmp）

题目链接：https://cn.vjudge.net/contest/276379#problem/J

感觉讲的很好的一篇博客：https://subetter.com/articles/extended-kmp-algorithm.html

题目大意：这是一个编译密码的题目，首先给你26个字母分别重新编码后的对应的字母，然后再给你一个字符串，字符串的前一部分是编译过后的，后一部分是编译之前的，但是后一部分可能会有损失，问你用尽量少的字符，将整个字符串补起来，也就是前面是暗文，后面是明文。

具体思路：扩展kmp的裸题，我们可以另外开一个字符，这个字符存储的是编译过后的，我们现在把初始密码串比喻成s1，编译过后的密码串比喻成s2，这个样的话，我们直接找出s2中的后缀中，满足是s1的前缀的最长的找出来，这个就是残缺的暗文，前面的就是明文了。

对于扩展kmp的理解：首先说一下我理解的扩展kmp的作用，我们假设当前有一个字符串t，长度是len。t[i]代表的是以字符串的第i位开始，以t[len-1]为截止位置的t的子串，然后nex[i]的作用就是求t[i]和t的最大前缀和的匹配数。

其实extend的作用和nex的具体实现内容是一样的，因为在求nex的时候，我们当前是以t为模板串，t[i]是子串。在求extend的时候，我们是以t为模板串，s是对比串的。

AC代码：

 #include<iostream>

 #include<stack>

 #include<iomanip>

 #include<stdio.h>

 #include<cmath>

 #include<algorithm>

 #include<string>

 #include<map>

 #include<cstring>

 #include<vector>

 using namespace std;

 # define ll long long

 const int maxn = 1e6+;

 char str[maxn],com[maxn];

 char tmp[maxn];

 int nex[maxn],extend[maxn];

 map<char,char>vis;

 void getnex(int len)

 {

     int a=,p=;

     nex[]=len;//第0位是自己

     for(int i=; i<len; i++)

     {

         if(i>=p||i+nex[i-a]>=p)

         {

             if(i>=p)

                 p=i;

             while(p<len&&tmp[p]==tmp[p-i])

                 p++;

             nex[i]=p-i;

             a=i;

         }

         else

             nex[i]=nex[i-a];

     }

 }

 void exkmp(int len1,int len2)

 {

     getnex(len2);

     int a=,p=;

     for(int i=; i<len1; i++)

     {

         if(i>=p||i+nex[i-a]>=p)

         {

             if(i>=p)

                 p=i;

             while(p<len1&&p-i<len2&&str[p]==tmp[p-i])

                 p++;

             extend[i]=p-i;

             a=i;

         }

         else

             extend[i]=nex[i-a];

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%s",com);

         scanf("%s",str);

         for(int i=; i<; i++)

         {

             vis[com[i]]='a'+i;

         }

         int len=strlen(str);

         for(int i=; i<len; i++)

         {

             tmp[i]=vis[str[i]];

         }

         exkmp(len,len);

         int i;

         for( i=;i<len;i++){

         if(i+extend[i]>=len&&i>=extend[i])break;//求满足情况的前缀

         }

         for(int j=;j<i;j++){

                 printf("%c",str[j]);

         }

         for(int j=;j<i;j++){

                 printf("%c",vis[str[j]]);

         }

         printf("\n");

     }

     return ;

 }

巴特西

J - Clairewd’s message HDU - 4300（扩展kmp）

最新文章

热门文章