CF126B

CF126B Password

题意：

给出一个字符串 H，找一个最长的字符串 h，使得它既作为前缀出现过、又作为后缀出现过、还作为中间的子串出现过。

解法:

沿着 $ next_n $ 枚举字符串，如果这个值在 $ next_I (i < n)$ 中出现合法。

预处理出 $ next $ 数组后记录那些值在 $ next $ 当中出现过，从 $ next_n $ 开始判断，如果不合法则从i 跳到 $ next_i $ 继续判断。

CODE:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<set>

using namespace std;

const int N = 1e6 + 10;

set<int > st;

int len,nxt[N];

char ch[N];

bool flag;

void kmp() {

    nxt[0] = nxt[1] = 0;

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

        int j = nxt[i];

        while(j && ch[i] != ch[j]) j = nxt[j];

        nxt[i + 1] = (ch[j] == ch[i] ? j + 1 : 0);

    }

}

int main() {

    scanf("%s",ch+1);

    len = strlen(ch + 1);

    kmp();

    st.clear();

    for(int i = 1 ; i <= len ; i++)

        st.insert(nxt[i]);

    flag = 0;

    int j = len;

    while(nxt[j]) {

        if(st.count(nxt[j])) {

            flag = 1;

            for(int i = 1 ; i <= nxt[j] ; i++)

                printf("%c",ch[i]);

            puts("");

            break;

        }

        j = nxt[j];

    }

    if(!flag) puts("Just a legend");

    return 0;

}

巴特西

CF126B

CF126B Password

题意：

解法:

CODE:

最新文章

热门文章