[kuangbin带你飞]专题十六 扩展kmp - K - Cl

题目:K - Clairewd’s message

题目大意

• 输入T组数据
• 每组第一行是解码方式，有26位，对应26字母，如第二个样例：qwertyuiopasdfghjklzxcvbnm，所表达的解码方式就是q->a,w->b,e->c...
• 第二行是一个，密文+明文的字符串，密文是完整的，明文可能是不完整的。
• 要求输出最短的完整信息，也就是密文+完整的明文。

这题真的是阅读题，看半天看不懂什么意思

解题思路

思路参考:[kuangbin] HDU 4300 Clairewd’s message（扩展KMP）

• 用map来转译
• 找到密文最短（明文最长）的分割点。
• 转译一次第二行字符串，那么前缀的完整密文被转译成明文，转译串作为模式串，原串作为模式串进行一次扩展kmp。
• 遍历extend，当i+extend[i]>=length（i开始的前缀一定要到字符串末尾，因为要匹配的是原串后段的明文）与i>=extend[i] (i点一定超过一半，前半段一定不会是明文)同时满足时，找到分割点。

AC代码

#include<iostream>
#include<map>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=100002;
void GetNEXT(string T,int n,int NEXT[]){
    int len = n;
    int a = 0 ;
    int j = 0 ;
    int i = 0 ;
    int p = 0 ;
    NEXT[0] = len;
    for(j=-1,i=1;j<=len,i<len;i++,j--){
        if(j<0||i+NEXT[i-a]>=p){
            if(j<0){
                j = 0;
                p = i;
            }
            while(j<len&&T[j] == T[p]){
                j++;p++;
            }
            NEXT[i] = j;
            a = i;
            
        }else{
            NEXT[i] = NEXT[i-a];
        }
    }
    
}


void GetExtend(string S,string T,int extend[],int NEXT[]){
    GetNEXT(T,T.length(),NEXT);
    int i,j,p,a,slen,tlen;
    slen = S.length();
    tlen = T.length();
    for(j=-1,i=0;i<slen;i++,j--){
        if(j<0||i+NEXT[i-a]>=p){
            if(j < 0){
                p = i ;
                j = 0 ;
            }
            
            while(p<slen&&j<tlen&&S[p] == T[j]){
                p++,j++;
            }
            extend[i] = j;
            a = i;
        }else{
            extend[i] = NEXT[i-1];
        }
    }
}


map<char,char> mapp;

int main()
{   
    char tab[MAXN];
    char str[MAXN];
    char c[MAXN];
    int T;
    cin>>T;
    while(T--){
//      cin>>tab>>str; 
        scanf("%s%s",&tab,&str);
        int len = strlen(str);
        for(int i = 0 ;i<strlen(tab);i++)
            mapp[tab[i]] = 'a'+i;
        for(int i = 0 ;i<len;i++)
            c[i] = mapp[str[i]];
        int extend[MAXN]={0};
        int NEXT[MAXN] ={0};
        GetExtend(str,c,extend,NEXT);
        int k=0;
        for(k=0;k<len;k++){
            if(k+extend[k]>=len&&k>=extend[k]) break;
        }
         for(int i=0;i<k;i++)printf("%c",str[i]);
        for(int i=0;i<k;i++)printf("%c",mapp[str[i]]);
        printf("\n");
    }
    return 0;
}

这种要操作字符的时候，用string总是会出现奇怪的问题，还是直接用字符数组好。

主要是练习扩展kmp，其实关键就在找分割点，用kmp的next数组也可以实现。