hdu 4300 Clairewd’s message（kmp/扩展kmp）

题意：真难懂。。

给出26个英文字母的加密表，明文中的'a'会转为加密表中的第一个字母，'b'转为第二个，...依次类推。

然后第二行是一个字符串（str1），形式是密文+明文，其中密文一定完整，而明文可能不完整（也可能没有）。

求出最短的完整的字符串（密文+明文）。

思路：

1.用kmp来做：

首先肯定的是，给定的串中明文长度一定小于等于密文。也就是说明文长度小于等于总长的一半。

于是，取总长的后一半作为主串，然后把串反翻译一遍得到str2，然后用str2与str1的后一半进行匹配。首次把str1的后一半匹配完的位置即是给定的串中明文开始的位置。

因为是首次，所以保证了前面的密文长度最小，即总长度最小。

然后输出密文+明文，即可。

2.用扩展kmp来做：

//next[i]:x[i...m-1]与x[0...m-1]的最长公公前缀

//extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀

可以用extend数组，根据它的意义，str1作为y，str2作为x，当 i+extend[i]==len1时代表y中的从i到结尾均与x的开头匹配，如果此时i大于串长度的一半，则满足条件。

此时的i即为实际密文（明文）的长度，然后按要求输出答案即可。

kmp：

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

#define MaxSize 100005

int _next[MaxSize];

void GetNext(char t[]){//求next数组

    int j,k,len;

    j=;

    k=-;

    _next[]=-;

    len=strlen(t);

    while(j<len){

        if(k==-||t[j]==t[k]){

            ++j;

            ++k;

            _next[j]=k;//此句可由优化替代

            /*优化（仅保证求KMPIndex时可用。谨慎使用。）

            if(t[j]!=t[k])next[j]=k;

            else next[j]=next[k];

            */

        }

        else k=_next[k];

    }

}

int KMPIndex(char s[],char t[]){//求子串首次出现在主串中的位置

    int i,j,lens,lent;

    i=j=;

    lens=strlen(s);

    lent=strlen(t);

    while(i<lens&&j<lent){

        if(j==-||s[i]==t[j]){

            ++i;

            ++j;

        }

        else j=_next[j];

    }

    //if(j>=lent)return i-lent;

    //else return -1;

    return j;

}

int main(){

    char str[],str1[MaxSize],str2[MaxSize];

    char cstr[];//密文->明文

    int t,i,len1,len11,num;

    scanf("%d",&t);

    while(t--){

        scanf("%s%s",str,str1);

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

            cstr[str[i]-'a']='a'+i;

        len1=strlen(str1);//

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

            str2[i]=cstr[str1[i]-'a'];

        str2[i]='\0';

        GetNext(str2);//求子串的next数组

        len11=len1/;//假设串中明文长度

        num=KMPIndex(str1+len1-len11,str2);//串中的明文个数

        printf("%s",str1);

        len11=len1-num;//实际密文（明文）长度

        for(i=num;i<len11;++i){

            printf("%c",str2[i]);

        }

        printf("\n");

    }

    return ;

}

扩展kmp：

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

#define MaxSize 100005

int _next[MaxSize],extend[MaxSize];

//扩展kmp

//next[i]:x[i...m-1]与x[0...m-1]的最长公公前缀

//extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀

void pre_EKMP(char x[],int m,int _next[]){

    _next[]=m;

    int j=;

    while(j+<m&&x[j]==x[j+])j++;

    _next[]=j;

    int k=;

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

        int p=_next[k]+k-;

        int L=_next[i-k];

        if(i+L<p+)_next[i]=L;

        else{

            j=max(,p-i+);

            while(i+j<m&&x[i+j]==x[j])j++;

            _next[i]=j;

            k=i;

        }

    }

}

void EKMP(char x[],int m,char y[],int n,int _next[],int extend[]){

    pre_EKMP(x,m,_next);

    int j=;

    while(j<n&&j<m&&x[j]==y[j])j++;

    extend[]=j;

    int k=;

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

        int p=extend[k]+k-;

        int L=_next[i-k];

        if(i+L<p+)extend[i]=L;

        else{

            j=max(,p-i+);

            while(i+j<n&&j<m&&y[i+j]==x[j])j++;

            extend[i]=j;

            k=i;

        }

    }

}

int main(){

    char str[],str1[MaxSize],str2[MaxSize];

    char cstr[];//密文->明文

    int t,i,j,len1,len11,num;

    scanf("%d",&t);

    while(t--){

        scanf("%s%s",str,str1);

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

            cstr[str[i]-'a']='a'+i;

        len1=strlen(str1);

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

            str2[i]=cstr[str1[i]-'a'];

        str2[i]='\0';

        EKMP(str2,len1,str1,len1,_next,extend);

        len11=(len1+)/;//假设串中密文长度

        for(i=len11;i<len1;++i)//从一半+1开始看，因为密文长度大于等于一半

            if(i+extend[i]==len1)break;//此时i为实际密文（明文）长度

        printf("%s",str1);

        for(j=len1-i;j<i;++j){

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

        }

        printf("\n");

    }

    return ;

}

巴特西

hdu 4300 Clairewd’s message（kmp/扩展kmp）

最新文章

热门文章