题目:https://codeforces.com/problemset/problem/1536/B
题目大意:给你一串字符串,然后按字典序求第一个没在这个字符串中出现的子串,如样例:qaabzwsxedcrfvtgbyhnujmiklop,a-z都出现了,aa出现了,ab出现了,ac没出现,答案就是ac。
题解:先用set保存出现过后的子串,然后进行判断
因为n<1000<27+27^2+27^3,所以子串最长长度为3
//#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <set>
#include <string>
using namespace std;
typedef long long int ll;set<string>s;
int main()
{int t;cin >> t;while (t--){int n;string b;cin >> n >> b;s.clear();//1000<26+26^2+26^3for (int j = 1; j <= 3; j++)//字串长度{for (int i = 0; i < n; i++){string a;//min(n,i + j)若超出n则用nint minn = min(n, i + j);;for (int k = i; k < minn; k++){a += b[k];}//存下所有子串s.insert(a);}}string ans = "a";while (1){if (!s.count(ans))//判断在不在set里面{cout << ans << endl;break;}int len = ans.size();if (ans[len - 1] == 'z')//如果最后为z{while (len >= 1 && ans[len - 1] == 'z')//前一位还是z,进行循环{ans[len - 1] = 'a';len--;}if (len == 0)//循环到最前方,进行加法{ans = 'a' + ans;continue;}if ( ans[len - 1] != 'z')//循环到中间,进行加法{ans[len - 1]++;}}else{ans[ans.size() - 1]++;//不为z直接加}}}
}