高塔

Translation by KSkun

原题：問題「高層タワー」 | エンジニアが死滅シタ世界 〜アンドロイドとふたりぼっちで生きろ〜

问题描述

你在把一些单词组合成新的单词。
新单词由N个字符串按先后顺序结合而成。
为了避免新单词过于冗长，需要将前一个单词的末端与后一个单词的前端最长的相同子串合并起来。
例如，样例1中需要合并paiza、apple和letter三个单词，
前两个单词paiza和apple按要求合并后得到了paizapple这个单词。
再合并上后一个单词就得到了paizappletter。

注意，必须按从前到后的顺序合并，样例2中合并poh、p、oh时，
poh和p合并得到了pohp，此时再合并oh得到的是pohpoh。
请按照输入的先后顺序合并给出的N个字符串得到新单词。

输入格式

N 
w_1 
w_2 
... 
w_N

• 第一行包含一个整数N，表示需要合并的单词数量。
• 接下来的N行中，第i行给出第i个需要合并的单词字符串w_i。
• 输入共N + 1行，在输入的最后，包含一个换行符。

输出格式

输出N个单词按输入先后顺序结合成的新单词。

条件

• 2 ≦ N ≦ 100
• 对于每个给出的单词字符串w_i，都满足以下条件。
  • 1 ≦ w_i的长度 ≦ 100
  • w_i只由半角小写英文字母构成。

输入输出样例

输入输出样例1

输入：

3 
paiza 
apple 
letter

输出：

paizappletter

输入输出样例2

输入：

3 
poh 
p 
oh

输出：

pohpoh

题解

// Code by KSkun, 2019/1
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    LL res = 0, neg = 1; char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 10005;

int n, rlen = 0, len;
char res[MAXN], w[MAXN];

inline bool issame(int len) {
    for(int i = 1; i <= len; i++) {
        if(res[rlen - (len - i)] != w[i]) return false;
    }
    return true;
}

inline int solve(int len) {
    for(int i = std::min(rlen, len); i >= 1; i--) {
        if(issame(i)) return i;
    }
    return 0;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%s", w + 1);
        len = strlen(w + 1);
        int r = solve(len);
        for(int i = 1; i <= len - r; i++) {
            res[rlen + i] = w[r + i];
        }
        rlen += len - r;
    }
    printf("%s", res + 1);
    return 0;
}