首页 > 代码库 > HDU 4886 TIANKENG’s restaurant(Ⅱ)
HDU 4886 TIANKENG’s restaurant(Ⅱ)
题意:
一个字符串有许多子串 现要找出最短的字典序最小的不是它的子串的串 这个长串只有A~H字母
思路:
YY一下答案串能有多长 8^7就比长串长了 所以也就是7的长度
那么只需要枚举长度 利用哈希判定字符串出现的问题 如何哈希呢?
一共就8个字母明显搞成8进制数 例如 AABCAD 就是 001203(8) 只有7的长度连int都不会爆 哈希稳稳的
而且通过hash值可以很简单的转化回字符串 输出也方便
代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 1000010 char str[N]; int hash[N], num[N]; int ans, end; int main() { int t, i, j, len; scanf("%d", &t); while (t--) { scanf("%s", str + 1); len = strlen(str + 1); memset(hash, 0, sizeof(hash)); memset(num, 0, sizeof(num)); end = 8; for (j = 1; j <= 7; j++) { for (i = len; i >= j; i--) { hash[i] = hash[i - 1] * 8 + str[i] - 'A'; num[hash[i]]++; } for (i = 0; i < end; i++) { if (!num[i]) { ans = i; goto FZC; } num[i] = 0; } end *= 8; } FZC: i = 0; while (j--) { str[i++] = ans % 8 + 'A'; ans /= 8; } for (j = i - 1; j >= 0; j--) putchar(str[j]); puts(""); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。