翻译
如果一个字符串的子串出现的次数大于任何子串出现的次数,那么这个子串就是 most frequent。给 n 个 most frequent 子串,问最短的原串。如果有多个最短原串,取字典序最小的那个。
分析
根据 most frequent 的定义,可知一个字母不会重复出现。可用两个数组标记,每个字母(共26个)是否有前缀或者是否可以作为 head,和其后缀是什么。遍历所有子串:
首字母,判断其是否有前缀,如果没有前缀设置成可作为 head ,如果有前缀则不变。
非首字母,如果前一个字母是没有后缀并且当前字母没有前缀,则给前一个字母设置后缀,当前字母设置为有前缀。如果前一个字母有后缀,并且后缀就是当前字母,则不操作。否则,设置成失败状态,这组数据输出 NO。
在遍历完成后,从 'a' 到 'z' 遍历,找出可以作为 head 的字母放进数组里面。依次根据后缀标记拼出字符串。
还需要判断拼出来的字符串是否包含所有子串出现过的字符,如果有未包含的子串则说明后缀链有环也就是会出现重复的字母,这种情况不符合定义。输出 NO。
这样得到的字符串一定是字典序最小的,而因为不会有重复字母,所以符合要求的串一定是最短的。
代码(C++)
//
// main.cpp
// ACM
//
// Created by Tconan on 2017/11/8.
// Copyright © 2017年 Tconan. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
char str[100010];
int n = 0;
int nexT[27] = {0};
int last[27] = {0};
int number = 0;
int start[27] = {0};
int len = 0;
char s[100010];
bool isUsed[27] = {false};
int main(int argc, const char * argv[]) {
cin >> n;
bool abort = false;
for (int i=0; i<n; ++i) {
scanf("%s", str);
if (abort) {
continue;
}
for (int i=0; i<=strlen(str); ++i) {
if (i == 0) {
if (last[str[i] - 'a' + 1] == 0) {
last[str[i] - 'a' + 1] = -1;
}
continue;
}
isUsed[str[i-1] - 'a' + 1] = true;
if (i == strlen(str)) {
continue;
}
if (nexT[str[i-1] - 'a' + 1] == 0 && last[str[i] - 'a' + 1] != 1) {
last[str[i] - 'a' + 1] = 1;
nexT[str[i-1] - 'a' + 1] = str[i] - 'a' + 1;
} else if (nexT[str[i-1] - 'a' + 1] == str[i] - 'a' + 1) {
continue;
} else {
abort = true;
break;
}
}
}
for (int i=1; i<=26; ++i) {
if (last[i] == -1) {
start[number++] = i;
}
}
if (abort) {
cout<<"NO"<<endl;
} else {
for (int i=0; i<number; ++i) {
int pos = start[i];
s[len ++] = pos + 'a' - 1;
isUsed[pos] = false;
while (nexT[pos] != 0) {
pos = nexT[pos];
isUsed[pos] = false;
s[len ++] = pos + 'a' - 1;
}
}
s[len ++] = '\0';
for (int i=1; i<=26; ++i) {
if (isUsed[i]) {
abort = true;
}
}
if (abort) {
cout<<"NO"<<endl;
} else {
cout<<s<<endl;
}
}
}