- POJ 3096 - Surprising Strings
- Time: 1000MS
- Memory: 65536K
- 难度: 中级
- 分类: 基础算法
0x00 POJ 原题
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 0-pairs are ZG, GB, and BG. Since these three pairs are all different, ZGBG is 0-unique. Similarly, the 1-pairs of ZGBG are ZB and GG, and since these two pairs are different, ZGBG is 1-unique. Finally, the only 2-pair of ZGBG is ZG, so ZGBG is 2-unique. Thus ZGBG is surprising. (Note that the fact that ZG is both a 0-pair and a 2-pair of ZGBG is irrelevant, because 0 and 2 are different distances.)
Acknowledgement: This problem is inspired by the “Puzzling Adventures” column in the December 2003 issue of Scientific American.
Input
The input consists of one or more nonempty strings of at most 79 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
0x10 题目概述
定义 D-pairs 表示取字符串 s 中相距为 D 的两个字母所构成的字母对，该字母对中两个字母的位置顺序与他们在主串 s 中的位置顺序一致
定义 D-unique 表示，若从字符串 s 中取出所有相距为 D 的字母对 D-pairs，且这些 D-pairs 都是独一无二的，那么成字符串 s 是一个 D-unique 串
D 的取值范围为 0 ~ s.len()-2
假如字符串 s 对于所有的 D 都有 D-unique 成立，则字符串 s 是令人惊讶的
现在输入一些字符串，问他们能不能令人惊讶
0x20 解题思路
令人惊讶的中级水题= =
用 STL 的 map 标记 D-unique 是否重复出现就 OK 了
也可以用 ASCII 标记，取两个大写字母的 ASCII 构成一个四位数作为 key 就可以了，比 map 快一点点
层次关系：
- 对于某个 D，当所有 D-pairs 都不同时，s 是 D-unique
- 对于所有 D，s 都有 D-unique 时，它是 surprising string
注意：
- 长度小于等于 2 的 s 都是 surprising string
- 其实我感觉这题暴力也能 AC= =，S 最大长度也就 79…
0x30 AC 源码
0x31 解题方法一：STL<map> 标记
/*STL<map>标记*/
//Memory Time
//212K 16MS
#include<iostream>
#include<string>
#include<map>
using namespace std;
int main(void)
{
char s[80];
while(cin>>s && s[0]!='*')
{
int len=strlen(s);
if(len<=2) //长度小于等于2的串必定是surprising String
{
cout<<s<<" is surprising."<<endl;
continue;
}
bool mark=true; //标记s是否为Surprising String
for(int d=0;d<=len-2;d++) //d为当前所选取的两个字母之间的距离，d(max)=len-2
{
map<string,bool>flag;
bool sign=true; //标记D-pairs字母对是不是D-unique
for(int i=0;i<=len-d-2;i++) //i为所选取的两个字母中第一个字母的下标
{
char pair[3]={s[i],s[i+d+1],'\0'}; //构成D-pairs字母对
if(!flag[ pair ])
flag[ pair ]=true;
else
{
sign=false; //存在相同的D-pairs,该字母对不是D-unique
break;
}
}
if(!sign)
{
mark=false; //存在非D-unique，s不是Surprising String
break;
}
}
if(mark)
cout<<s<<" is surprising."<<endl;
else
cout<<s<<" is NOT surprising."<<endl;
}
return 0;
}0x32 解题方法二：ASCII 标记
/*ASCII标记*/
//Memory Time
//212K 0MS
#include<iostream>
#include<string>
using namespace std;
int main(void)
{
char s[80];
while(cin>>s && s[0]!='*')
{
int len=strlen(s);
if(len<=2) //长度小于等于2的串必定是surprising String
{
cout<<s<<" is surprising."<<endl;
continue;
}
bool mark=true; //标记s是否为Surprising String
for(int d=0;d<=len-2;d++) //d为当前所选取的两个字母之间的距离，d(max)=len-2
{
bool flag['Z'*100+'Z'+1]; //标记D-pairs字母对
memset(flag,false,sizeof(flag));
bool sign=true; //标记D-pairs字母对是不是D-unique
for(int i=0;i<=len-d-2;i++) //i为所选取的两个字母中第一个字母的下标
{
int pair=s[i]*100+s[i+d+1]; //D-pairs字母对的ASCII码所构成的四位数
if(!flag[pair])
flag[pair]=true;
else
{
sign=false; //存在相同的D-pairs,该字母对不是D-unique
break;
}
}
if(!sign)
{
mark=false; //存在非D-unique，s不是Surprising String
break;
}
}
if(mark)
cout<<s<<" is surprising."<<endl;
else
cout<<s<<" is NOT surprising."<<endl;
}
return 0;
}
