codeforces 126B B. Password（kmp+dp）

题目链接：

codeforces 126B

题目大意：

给出一个字符串，找出一个子串既是它的前缀，也是它的后缀，还是一个非后缀也非前缀的子串。

题目分析：

• 本来挺简单的一个题，最开始想复杂了，还用了后缀数组，醉了。
• 这个题主要用的是kmp的next数组，首先我们要了解next数组的定义，next[i]表示以i为末尾的子串的后缀与能够匹配的整个串的最长的前缀。
• 然后我们可以知道后缀与前缀的最长相同的长度，现在是满足后缀和前缀的最长子串的情况。
• 然后我们利用hash除了以最后一个字符结尾的情况所有的与前缀匹配的长度。
• 最后我们利用next数组的性质，如果当前的匹配的长度在hash表中找不到，那么证明不存在非前缀与非后缀的子串符合条件，那么x=next[x]，也就是跳转到当前位置失配的重新匹配的位置（免去重复匹配的部分），也就是小于当前情况的最大的子串的后缀和前缀匹配的情况，然后再查hash表。知道找到答案为止，找不到答案证明不存在解。

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 1000007

using namespace std;

char s[MAX];
int next[MAX];
int hash[MAX];

void kmp ( int n )
{
    memset ( next , 0 , sizeof ( next ) );
    for ( int i = 2 ; i <= n ; i++ )
    {
        int k = next[i-1];
        while ( k && s[k+1] != s[i] ) k = next[k];
        if ( s[k+1] == s[i] ) next[i]=k+1;
    }
}

int main ( )
{
    while ( ~scanf ( "%s" , s+1 ) )
    {
        int n = strlen ( s+1 );
        kmp ( n );
        memset ( hash , 0  , sizeof ( hash ) );
        for ( int i = 2; i < n ; i++ )
            hash[next[i]] = 1;
        int x = next[n];
        while ( !hash[x] && x ) x = next[x];
        if ( !x ) printf ( "Just a legend" );
        else for ( int i = 1 ; i <= x ; i++ )
            printf ( "%c" , s[i] );
        puts ( "" );
    }

}