愛悠閑 > HDOJ 4300 Clairewd's message(擴展KMP)

HDOJ 4300 Clairewd's message(擴展KMP)

分類: ACM/Algorithms  |  作者: michaelalan 相關  |  發布日期 : 2015-03-12  |  熱度 : 62°

超級傳送門:鏈接地址


本題題意是給你一個字符對應表,再給一個密文和明文相連接的串(明文后綴可能缺失),求補全后的串。

比如樣例:

abcdefghijklmnopqrstuvwxyz
abcdab

為了方便,字符對應表是默認的。abcdab便是密文和明文相連接的串,記長度為m,我們需要找到分割點。

利用擴展KMP將該串所有后綴與該串前綴進行匹配,如果能匹配到最后一個字符,即k+P[k] == m,則該處可進行分割,找到最小的k值,即可進行最小分割。還要注意,k位置必須在串的后一半,即串中密文字符數不能少于明文字符數。匹配的時候前綴部分要根據字符轉換表進行轉換(即將前綴看成密文,將其轉換為明文,再與后綴部分明文進行匹配)。


代碼如下:

#include <cstdio>
#include <cstring>

using namespace std;

int P[100010];
char table[26], rev_table[26];
char B[100010];

int ex_preprocess(char* B, int* P, int m = -1)
{
    int a = 0, p, L;

    if (m == -1)
        m = strlen(B);

    P[0] = m;
    while (a < m - 1 && B[a] == table[B[a + 1] - 'a'])
        a++;
    P[1] = a;
    a = 1;

    for (int k = 2; k < m; k++)
    {
        p = a + P[a] - 1;
        L = P[k - a];
        if ((k - 1) + L >= p)
        {
            int j = (p - k + 1) > 0 ? (p - k + 1) : 0;

            while (k + j < m && table[B[k + j] - 'a'] == B[j])
                j++;

            P[k] = j;
            a = k;
        }
        else
            P[k] = L;

        if (k > ((m - 1) >> 1) && k + P[k] == m)
            return k;
    }
    return m;
}

void make_rev_table(char table[26], char rev_table[26])
{
    for (int i = 0; i < 26; i++)
        rev_table[table[i] - 'a'] = 'a' + i;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%s%s", table, B);

        make_rev_table(table, rev_table);
        int m = strlen(B);
        int index = ex_preprocess(B, P, m);
        for (int i = 0; i < index; i++)
            printf("%c", B[i]);
        for (int i = 0; i < index; i++)
            printf("%c", rev_table[B[i] - 'a']);
        printf("\n");
    }
    return 0;
}


快乐彩中奖说明