题目原文
瑞神今年大三了，他在寒假学会了英文的26个字母，所以他很兴奋！于是他让他的朋友TT考考他，TT想到了一个考瑞神的好问题：给定一个字符串，从里面寻找连续的26个大写字母并输出！但是转念一想，这样太便宜瑞神了，所以他加大了难度：现在给定一个字符串，字符串中包括26个大写字母和特殊字符‘?’，特殊字符‘?’可以代表任何一个大写字母。现在TT问你是否存在一个位置连续的且由26个大写字母组成的子串，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现的符合要求的子串，并且要求，如果有多组解同时符合位置最靠左，则输出字典序最小的那个解！如果不存在，输出-1！这下HRZ蒙圈了，他刚学会26个字母，这对他来说太难了，所以他来求助你，请你帮他解决这个问题，报酬是可以帮你打守望先锋。
说明：字典序先按照第一个字母，以A、B、C......Z的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，SIGH和SIGHT），那么把短者排在前。例如
AB??EFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABDCEFGHIJKLMNOPQRSTUVWXYZ
上面两种填法，都可以构成26个字母，但是我们要求字典序最小，只能取前者。注意，题目要求的是第一个出现的，字典序最小的！
输入格式
输入只有一行，一个符合题目描述的字符串。
输出格式
输出只有一行，如果存在这样的子串，请输出，否则输出-1
样例输入1
ABC??FGHIJK???OPQR?TUVWXY?
样例输出1
ABCDEFGHIJKLMNOPQRSTUVWXYZ
样例输入2
AABCDEFGHIJKLMNOPQRSTUVW??M
样例输出2
-1
| 数据点 | 字符串长度 |
|---|---|
| 1，2，3 | 24 |
| 4，5，6 | 10000 |
| 7，8，9，10 | 106 |
解题思路
本题要求如果存在连续的26个字母，则输出字典序最小的选择，否则输出-1。
定义结构体存储输入的每个字符和其对对应的位置（从1开始记录），定义l 和r（初始值均为1）记录当前选中字符串的左右两个位置，每读入一个字符，r++。
利用judge函数的opt=1操作将当前字母的位置存储，并用a[]给对应字母打上标记。如果输入过程中遇到了已经打上标记的字母，则从t中获取该字母前一次出现的位置，并将t之前的字母标记清空，且l=t+1,再将当前位置标记。
由于结束时r会多加一次，所以当r-l=26时说明找到了对应字符串，直接break退出，若直到输入结束，r-l（取出字符个数）仍小于26说明不存在指定字符串。
由于要求最小字典序输出。故输出时如果遇到"?"，就扫描标记数组a[]，找到第一个未被标记的字母，并打上标记（可以省去），记录当前标记的位置，下次再遇到“？”就从标记位置继续往后查找下一个未被标记字母。
实现代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 10;
struct word {
char x;
int index;
}m[maxn];
int t = 0;
bool a[28];//标记选取的26个子母出现次数
int b[28];//标记每个字母最近位置
char c[28] = { '0','A','B','C','D','E','F','G','H','I','J',
'K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };
bool judge(word p, int& t, int opt) {//1为放入，0为取出
if (opt == 1)
{
if (p.x == '?')
{
return 1;
}
int q = p.x - 'A' + 1;
if (p.x == c[q] && a[q] == 1)
{
t = b[q];
return 0;
}
if (p.x == c[q] && a[q] != 1)
{
b[q] = p.index;
a[q] = 1;
return 1;
}
}
else if (opt == 0)
{
if (p.x == '?')
{
//s--;
return 1;
}
int q = p.x - 'A' + 1;
if (p.x == c[q] && a[q] == 1)
{
b[q] = 0;
a[q] = 0;
return 0;
}
}
}
int main()
{
int i = 0;
int l = 1, r = 1;
memset(m, 0, sizeof(m));
while (scanf("%c", &m[++i].x) != EOF)
{
if (r - l == 26)
break;
//判断输入是否结束
if (m[i].x != '?' && (m[i].x<'A' || m[i].x>'Z'))
break;
m[i].index = i;
int d;
if (!judge(m[i], t, 1))
{
for (int j = l; j < t+1; j++)
judge(m[j], t, 0);
judge(m[i], d, 1);
l = t + 1;
}
r++;
}
if (r - l < 26)
{
cout << -1 << endl;
//cout << r << " " << l << endl;
exit(0);
}
else if (r - l == 26)
{
int k = 1;
for (int i = l; i <r; i++)
{
if (m[i].x == '?')
{
for (int j = k; j <= 26; j++)
{
if (a[j] == 0)
{
k = j + 1;
printf("%c", c[j]);
a[j] = 1;
break;
}
}
}
else
{
printf("%c", m[i].x);
}
}
}
cout << endl;
return 0;
}
小结
选用适宜的基础算法可以更快地解决问题，如果本题采用尺举法计算会比自己想算法更加快捷简单，消耗时间会大大减少。
