题目:
所述d-对字母的字符串的是有序对的是彼此的距离d字母。字符串是d-独特的,如果所有的d-对是不同的。的字符串是令人惊讶的,如果它是d-独特的每一个可能的距离D.
考虑串ZGBG。其0对是ZG,GB和BG。由于这三对都是不同的,ZGBG是0,唯一的。类似地,1-对ZGBG的是ZB和GG,并且由于这两个对是不同的,ZGBG是1-唯一的。最后,只有2对ZGBG的是ZG,所以ZGBG是2-唯一的。因此ZGBG是令人惊讶的。 (注意这样一个事实,ZG既是0对和2对ZGBG的是无关紧要的,因为0和2是不同的距离。)
确认:此问题是由科学美国人的2003年12月号的“迷宫历险记”栏目的启发。
输入
输入包括至多79个大写字母的一个或多个非空字符串,由本身的线的每个字符串,随后仅含有一个星号的线的所述输入信号的结束。
产量
为字母,输出它是否被使用以下所示的精确的输出格式奇每个字符串。
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.
解题思路:这个题主要是用STL中的map容器,首先每一次把间隔为0、1、2…的串找出来,然后存入map容器中,map 的型号为<string int 》,然后去遍历一遍间隔不同的map,如果出现相同字符串大于2的就输出not;
程序代码:
#include<iostream> #include<algorithm> #include<map> #include<string> #include<string.h> using namespace std; int main() { char s[100],s1[100]; int n,i,j,k,t,flag,count; char x,y; while(scanf("%s",s)!=EOF) { if(s[0]=='*') break; flag=0; n=strlen(s); for(i=1;i<=n-2;i++) { k=0; t=1; map<string,int> m1; while(k+i<n) { s1[0]=s[k]; s1[1]=s[k+i]; m1[s1]++; k++; } map<string,int>::iterator it1; for(it1=m1.begin();it1!=m1.end();it1++) { if((*it1).second>=2) { flag=1; break; } } if(flag==1) break; } if(flag==0) printf("%s is surprising.\n",s); else printf("%s is NOT surprising.\n",s); } return 0; }