KMP HDOJ 4300 Clairewd's message

题目传送门

题意：完全不懂，最后还是看题解才理解了。第一行字符串是密文变成明文的规则，比如第二个样例：“qwertyuiopasdfghjklzxcvbnm”，‘q'对应的明文为’a'，'w'对应'b'....... 第二行是密文+明文的形式，明文有密文转换来，但不完整，求原来最小的可能文本。

分析：将密文+明文都当做密文转成明文，那么转换后的字符串前缀密文的部分解密，和原来的字符串的后缀明文匹配，从原来字符串的后半部分和转换之后的字符串的开头开始匹配，得到的是明文(密文)的长度。详细解释

收获：题目读不懂多读几遍，再不行yy题意，想想会涉及什么算法

代码：

/************************************************

* Author        :Running_Time

* Created Time  :2015-8-24 19:42:24

* File Name     :A.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

char ch[30], m[30], s[N], rs[N];

int fail[N];

void get_fail(char *P, int lenp)  {

    int i = 0, j = -1;  fail[0] = -1;

    while (i < lenp)    {

        if (j == -1 || P[j] == P[i])    {

            i++;    j++;    fail[i] = j;

        }

        else    j = fail[j];

    }

}

int KMP(char *T, char *P)   {

    int lent = strlen (T), lenp = strlen (P);

    get_fail (P, lenp);

    int i = 0, j = 0;

    while (i < lent)  {

        while (j != -1 && T[i] != P[j]) j = fail[j];

        i++; j++;

    }

    return j;

}

int main(void)    {

    int T;  scanf ("%d", &T);

    while (T--) {

        scanf ("%s%s", &ch, &s);

        for (int i=0; i<26; ++i)    {

            m[ch[i]-'a'] = 'a' + i;

        }

        int len = strlen (s);

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

            rs[i] = m[s[i]-'a'];

        }

        int k = KMP (s + (len + 1) / 2, rs);

        for (int i=0; i<len-k; ++i) printf ("%c", s[i]);

        for (int i=0; i<len-k; ++i) printf ("%c", rs[i]);

        puts ("");

    }

    return 0;

}

巴特西

KMP HDOJ 4300 Clairewd's message

最新文章

热门文章