URAL 1684. Jack’s Last Word

Author: 2015-11-18

ACM

, , ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1684

1684. Jack’s Last Word

Time limit: 0.5 second
Memory limit: 64 MB
Not long ago Jack read on a fence a word that was new and amusing for him. Jack liked it so much that he wanted to invent another amusing word, but no matter how hard he tried he couldn’t do it. All the words he could invent consisted of prefixes of the initial word and therefore didn’t please Jack. He continued to invent words that were longer and longer, but none of them was pleasing.
And now the time has come for Jack to have his last word.

Input

The first line contains the amusing word that was written on the fence. The second line contains Jack’s last word. The words are nonempty, consist of lower-case English letters, and are no longer than 75000 symbols.

Output

If Jack didn’t invent a new amusing word, output “No” in the first line. In this case, show Jack how to decompose his last word into several parts each of which is either the initial word or its nonempty prefix. Output these parts in the second line separating them with a space. If there is no such decomposition, output “Yes” in the only output line.

Samples

input output 
abracadabra
abrabracada

No
abr abracad a

abracadabra
arbadacarba

Yes
Problem Author: Dmitry Ivankov
Problem Source: USU Open Personal Contest 2009 (February 28, 2009)

2. 思路

给出两个字符串S1和S2，求S2是否完全由S1的前缀构成。如第一个测试例，S1 = abracadabra， S2 = abrabracada，S2可以拆分成“abr”、“abracad”和“a”三个子串，这三个字
串都是S1的前缀；S2也可以拆分成“abr”和“abracada”两个子串，同样也都是S1的前缀。

字符串匹配，使用KMP。用S1去匹配S2，如果发生不匹配，需要记录不匹配的位置用于最后的输出，注意S1和S2不一定等长，如果S1是S2的一个子串，完全匹配后还需要继续匹配S2的后续内容。

3. 代码

 

#include <cstdio>
#include <cstring>

const int MAX_LENGTH = 75010;

void solveP9e_JacksLastWord();
int kmp(char target[], char pattern[], int table[], int sep[]);
void buildTable(char pattern[], int table[]);

int main() {
    // freopen("test.txt", "r", stdin);
    solveP9e_JacksLastWord();
    return 0;
}

char target[MAX_LENGTH], pattern[MAX_LENGTH];
int table[MAX_LENGTH], sep[MAX_LENGTH];
void solveP9e_JacksLastWord() {
    scanf("%s", pattern);
    scanf("%s", target);

    buildTable(pattern, table);
    int result = kmp(target, pattern, table, sep);

    if (result < 0) {
        printf("Yes\n");
    } else {
        printf("No\n");
        int cnt = 0;
        for (int i = 0; i < result; ++i) {
            for (; cnt < sep[i]; ++cnt) {
                printf("%c", target[cnt]);
            }
            printf(" ");
        }
        int targetLen = strlen(target);
        while (cnt < targetLen) {
            printf("%c", target[cnt++]);
        }
        printf("\n");
    }
}

int kmp(char target[], char pattern[], int table[], int sep[]) {
    int m = 0, i = 0, cnt = 0, targetLen = strlen(target);

    while (m + i < targetLen) {
        if (pattern[i] == target[m + i]) {
            ++i;
        } else {
            if (table[i] > -1) {
                m = m + i - table[i];
                i = table[i];
                sep[cnt++] = m;
            } else {
                i = 0;
                ++m;
                return -1;
            }
        }
    }

    return cnt;
}

void buildTable(char pattern[], int table[]) {
    int pos = 2, cnd = 0, len = strlen(pattern);
    table[0] = -1;
    table[1] = 0;

    while (pos <= len) {
        if (pattern[pos - 1] == pattern[cnd]) {
            ++cnd;
            table[pos] = cnd;
            ++pos;
        } else if (cnd > 0) {
            cnd = table[cnd];
        } else {
            table[pos] = 0;
            ++pos;
        }
    }
}