[UVA][二分搜+KMP] 12467 - Secret Word＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2012-12-23 19:38:43| 人1,188| 回0 | 上一篇 | 下一篇

[UVA][二分搜+KMP] 12467 - Secret Word

推 0 收藏 0 0 站台

Problem G. Secret word

Alicia and Roberto like to play games. Today, Roberto is trying to guess a secret word that Alicia chose. Alicia wrote a long string S in a piece of paper and gave Roberto the following clues:

The secret word is a non-empty substring¹ of S (possibly equal to S).
S starts with the secret word reversed.

Roberto knows Alicia very well, and he’s sure that if there are several possible secret words that satisfy the clues above, Alicia must have chosen the longest one.

Can you help him guess the secret word?

Input

The first line of the input file contains a single integer number T ≤ 150, the number of test cases.

T lines follow, each with a single string S. S will only contain lowercase English letters. The length of S will not exceed one million characters.

Output

For each test case, output the secret word in one line.

Sample input and output

standard input	standard output

5 colombia abcdba neversayeven neveroddoreven listentothesilence	c ba even neveroddoreven sil

Explanation of the sample cases

colombia: if you take c and reverse it you get c. colombia starts with c, so this satisfies the two clues above. Furthermore, c is the longest word that satisfies the two clues so it must be the secret word.
abcdba: if you take ba and reverse it you get ab. abcdba starts with ab and there’s no longer substring that satisfies the two clues.
neversayeven: if you take even and reverse it you get neve. neversayeven starts with neve and there’s no longer substring that satisfies the two clues.
neveroddoreven: this case is a palindrome so if we reverse it we get the same string. neveroddoreven starts with neveroddoreven (since they are the same) and obviously there’s no longer substring that satisfies that, so this is the secret word.
listentothesilence: Notice the secret word might be somewhere in the middle of the big word.

Footnotes

¹A substring of S is defined as any consecutive sequence of characters belonging to S. For example, if S = abcd then a, abcd, ab, bc and bcd are some of the substrings of S but ac, aa, aabbccdd and dcba are not substrings of S.

Andrés Mejía-Posada, May 2012

答案度L行二分搜，接著使用 KMP 查 inv(前 L 字元)是否在面。

O(logL * L)

#include <stdio.h>
#include <string.h>
#define MaxL 1000005
char A[MaxL], B[MaxL];
int P[MaxL];
void KMPTable(const char *A) {
    int i, j;
    P[0] = -1, i = 1, j = -1;
    while(A[i]) {
        while(j >= 0 && A[j+1] != A[i])
            j = P[j];
        if(A[j+1] == A[i])
            j++;
        P[i++] = j;
    }
}
int KMPMatching(char A[], char B[], int la, int lb) { // B in A
    KMPTable(B);
    static int i, j, Alen, Blen;
    Alen = la, Blen = lb;
    for(i = 0, j = -1; i < Alen; i++) {
        while(j >= 0 && B[j+1] != A[i])
            j = P[j];
        if(B[j+1] == A[i])    j++;
        if(j == Blen-1)
            return 1;
    }
    return 0;
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", A);
        int la = strlen(A);
        int l = 1, r = la, m, i, j;
        while(l <= r) {
            m = (l+r)>>1;
            for(i = m-1, j = 0; i >= 0; i--, j++)
                B[j] = A[i];
            B[j] = '\0';
            if(KMPMatching(A, B, la, m))
                l = m+1/*, printf("%s %d\n", B, m)*/;
            else
                r = m-1;
        }
        for(i = l-2; i >= 0; i--)
            putchar(A[i]);
        puts("");
    }
    return 0;
}