Surprising Strings
2024-08-28 20:51:47
Surprising Strings
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: Accepted:
Description The D-pairs of a string of letters are the ordered pairs of letters that are distance D from each other. A string is D-unique if all of its D-pairs are different. A string is surprising if it is D-unique for every possible distance D. Consider the string ZGBG. Its -pairs are ZG, GB, and BG. Since these three pairs are all different, ZGBG is -unique. Similarly, the -pairs of ZGBG are ZB and GG, and since these two pairs are different, ZGBG is -unique. Finally, the only -pair of ZGBG is ZG, so ZGBG is -unique. Thus ZGBG is surprising. (Note that the fact that ZG is both a -pair and a -pair of ZGBG is irrelevant, because and are different distances.) Acknowledgement: This problem is inspired by the "Puzzling Adventures" column in the December issue of Scientific American. Input The input consists of one or more nonempty strings of at most uppercase letters, each string on a line by itself, followed by a line containing only an asterisk that signals the end of the input. Output For each string of letters, output whether or not it is surprising using the exact output format shown below. Sample Input ZGBG
X
EE
AAB
AABA
AABB
BCBABCC
*
Sample Output ZGBG is surprising.
X is surprising.
EE is surprising.
AAB is surprising.
AABA is surprising.
AABB is NOT surprising.
BCBABCC is NOT surprising.
Source Mid-Central USA
#include <iostream>
#include <cstdio>
#include<set>
#include <vector>
#include <cstring>
#include <list>
#include <queue>
#include <algorithm>
#include<functional>
#include <stack>
#define MAXN 200 + 3
#define INF 0x3f3f3f3f
using namespace std;
//直接枚举+hash+set 随便过
char s[MAXN];
inline int Hash(char a, char b)
{
return (a - 'a') * + b - 'a';
}
int main()
{
ios::sync_with_stdio();
while (cin >> s, s[] != '*')
{
set<int> S;
int L = strlen(s);
int l;
for (l = ; l < L; l++)
{
S.clear();
for (int i = ; i + l < L; i++)
S.insert(Hash(s[i], s[i + l]));
if (S.size() != L - l)
break;
}
if (l == L)
cout << s << " is surprising." << endl;
else
cout << s << " is NOT surprising." << endl;
}
return ;
}
最新文章
- nodejs中异常错误的处理方式
- 一张图轻松搞懂javascript event对象的clientX,offsetX,screenX,pageX区别
- MG--滚动的视觉差效果
- Opensource开源精神
- DataSanp的控制老大-DSServer
- 5.2 Adapter
- EntityFramwork(1) 源地址https://msdn.microsoft.com/zh-cn/data/jj193542
- Android 高级UI设计笔记14:Gallery(画廊控件)之 3D图片浏览
- JavaIO(01)File类详解
- [转载]ASP.NET MVC 3的分部视图
- MATLAB 误差函数erf(x)
- NoSQL选型
- poj 3667 Hotel (线段树)
- JQuery重要知识点
- CSS3 背景属性
- POJ 3261 可重叠k次最长重复子串
- 【原创】Aduino小车玩法全记录
- JAVA8 in Action:行为参数化,匿名类及lambda表达式的初步认知实例整理
- 校验金额、大小写字母、大写字母、合法uri、email
- Spring Security 重定向原理分析