jzoj 2937_监听还原_KMP

发布于 2017-09-08  938 次阅读

题目描述

Alice和Bob正在悄悄地给对方发信息，信息都是由英文小写字母组成的，他们约定，所有的字母都得经过一个字母表进行变换，以防泄漏。另一方面John却在监听。 John发现，Alice和Bob通信的时候，总是先发送加密后的密文，然后紧接着发送原文。 但是Alice和Bob似乎也意识到了似乎有人监听，有时候会随意中断了他们的通信。不过每次都是在发送完密文之后才停止传送的。也就是说，John截获到的信息是密文的全文以及前一部分原文。原文可能一个字符都没有，也可能原文的全文都被截获。 现在John比较头疼，他虽然已经得到了他们两个人通信的加密字母表，但是分不清楚什么地方是密文和明文的分界线。你能帮他还原回完整的传输内容吗？ 如果有多种可能时，John认为那个最短的信息才是原始的。

 

思路

这题就是一个纯暴力，但我用了KMP来暴力

这题的题目很难读懂

这题正解是用KMP中的next数组直接一次出解

俗话说:带break的暴力都是正解

 

#include 
#include 
#include 
#include 
using namespace std;
char a[30], s[1000005], b[30];
int p[1000005];
int main()
{    
    scanf("%s", a);
    for (int i = 0; i < 26; i++)
    {
        b[a[i] - 'a'] = char(i + 'a');
    }
    scanf("%s", s);
    int len = strlen(s);
    int j = -1;
    for (int i = 1; i < (len + 1) / 2; i++)
    {
        if (s[i] != s[j + 1] && j != -1) j = p[j];
        if (s[i] == s[j + 1]) j++;
        p[i] = j;
    }
    for (int i = 0; i < (len + 1) / 2; i++)
    {
        cout << s[i];
    }
    for (int i = (len + 1) / 2; i <= len; i++)
    {
        int jj = -1;
        int fl = 0;
        for (int ii = i; ii < len; ii++)
        {
            if (a[s[ii] - 'a'] != s[jj + 1] && jj != 0) 
            {
                break;
                jj = p[jj];
            }
            if (a[s[ii] - 'a'] == s[jj + 1]) jj++;
            if (jj == len - i - 1)
            {    
                fl = 1;
                break;
            }
        }
        if (fl || i == len)
        {
            for (int ii = 0; ii < i; ii++)
            {
                cout << b[s[ii] - 'a'];
            }
            break;
        }
        cout << s[i];
        if (s[i] != s[j + 1] && j != -1) j = p[j];
        if (s[i] == s[j + 1]) j++;
        p[i] = j;
    }
}

 

]]>