Link

点击打开ural题目连接

Mean

有一个原串和新串,把新串分割成几个字串,使得每个字串都是原串的前缀

Analyse

首先想到的是从前往后依次匹配原串的前缀,但是如果遇到原串为“abac”,新串为“abab”时,如果匹配了新串aba,那么剩下的b就无法匹配了,这样就会出现多种情况。如果反过来从后往前匹配,就不会出现这种情况。

这时可以利用kmp的next数组,每次从后往前找最大匹配的长度,如果遇到next数组为0的情况就不能匹配。

求next数组的时候可以把两个字符串拼接,中间插入‘#’即可,这样next数组的值一定是原串中的。

C++Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 80000;
int fail[maxn*2], lena, lenb;
char s[maxn*2];
vector<string> res;

void getFail(const char *s, int *f, int len) {
    f[0] = f[1] = 0;
    for(int i = 1; i < len; ++i) {
        int j = f[i];
        while(j && s[i] != s[j]) j = f[j];
        f[i+1] = s[i]==s[j] ? j+1 : 0;
    }
}

void init() {
    scanf("%s", s);
    lena = strlen(s);
    s[lena] = '#';
    scanf("%s", s + lena + 1);
    lenb = strlen(s);
    s[lenb] = 0;
    getFail(s, fail, lenb);
}


bool solve() {
    for(int i = lenb; i > lena + 1; ) {
        if(fail[i] == 0) return false;
        res.push_back(string(s + i - fail[i], s + i));
        i -= fail[i];
    }
    return true;
}

int main() {
    init();
    if(!solve()) puts("Yes");
    else {
        puts("No");
        for(int i = res.size()-1; i >= 0; --i)
            cout << res[i] << (i ? ' ' : '\n');
    }
    return 0;
}

欢迎留言