POJ3096-Surprising Strings

転載は出典を明記してください:優YoU   http://user.qzone.qq.com/289065406/blog/1307434869
 
大体の問題:
定義D-pairsは、文字列sにおける距離Dの2文字からなるアルファベット対を表し、このアルファベット対における2文字の位置順序は、主列sにおける位置順序と一致する
D-unique表現を定義し、文字列sからDのアルファベット対D-pairsをすべて取り出し、これらのD-pairsがユニークであれば、文字列sはD-unique列である
Dの取値範囲は0~s.len()-2
文字列sがすべてのDに対してD-uniqueが成立している場合、文字列sは驚くべき==
 
驚くべき文字列を入力します==
 
問題解決の考え方:
驚くべき中級水問題==
STLのmapタグD-uniqueで重複しているかどうかでOKです
ASCIIタグを使って、2つの大文字のASCIIを取って1つの4桁の数をkeyとして構成することもできて、mapより少し速くなります
 
階層関係:
あるDに対して、すべてのD-pairsが異なる場合、sはD-uniqueである
すべてのDに対してsがD-uniqueを持っている場合はsurprising string
 
なお、長さが2以下のsはsurprising stringである
 
実は私はこの暴力もAC==できると感じて、Sの最大の長さは79です...
 

 1 /*STL<map>  */
 2 
 3 //Memory Time 
 4 //212K   16MS 
 5 
 6 #include<iostream>
 7 #include<string>
 8 #include<map>
 9 using namespace std;
10 
11 int main(void)
12 {
13     char s[80];
14     while(cin>>s && s[0]!='*')
15     {
16         int len=strlen(s);
17         if(len<=2)  //      2     surprising String
18         {
19             cout<<s<<" is surprising."<<endl;
20             continue;
21         }
22 
23         bool mark=true;  //  s   Surprising String
24         for(int d=0;d<=len-2;d++)  //d                ，d(max)=len-2
25         {
26             map<string,bool>flag;
27 
28             bool sign=true;  //  D-pairs      D-unique
29             for(int i=0;i<=len-d-2;i++)  //i                  
30             {
31                 char pair[3]={s[i],s[i+d+1],'\0'};  //  D-pairs   
32                 
33                 if(!flag[ pair ])
34                     flag[ pair ]=true;
35                 else
36                 {
37                     sign=false;  //     D-pairs,      D-unique
38                     break;
39                 }
40             }
41             if(!sign)
42             {
43                 mark=false;  //   D-unique，s  Surprising String
44                 break;
45             }
46         }
47         if(mark)
48             cout<<s<<" is surprising."<<endl;
49         else
50             cout<<s<<" is NOT surprising."<<endl;
51     }
52     return 0;
53 }

 
 
=======華やかな分割線======
 
 

 1 /*ASCII  */
 2 
 3 //Memory Time 
 4 //212K   0MS 
 5 
 6 #include<iostream>
 7 #include<string>
 8 using namespace std;
 9 
10 int main(void)
11 {
12     char s[80];
13     while(cin>>s && s[0]!='*')
14     {
15         int len=strlen(s);
16         if(len<=2)  //      2     surprising String
17         {
18             cout<<s<<" is surprising."<<endl;
19             continue;
20         }
21         bool mark=true;  //  s   Surprising String
22         for(int d=0;d<=len-2;d++)  //d                ，d(max)=len-2
23         {
24             bool flag['Z'*100+'Z'+1];   //  D-pairs   
25             memset(flag,false,sizeof(flag));
26 
27             bool sign=true;  //  D-pairs      D-unique
28             for(int i=0;i<=len-d-2;i++)  //i                  
29             {
30                 int pair=s[i]*100+s[i+d+1];  //D-pairs    ASCII        
31 
32                 if(!flag[pair])
33                     flag[pair]=true;
34                 else
35                 {
36                     sign=false;  //     D-pairs,      D-unique
37                     break;
38                 }
39             }
40             if(!sign)
41             {
42                 mark=false;  //   D-unique，s  Surprising String
43                 break;
44             }
45         }
46         if(mark)
47             cout<<s<<" is surprising."<<endl;
48         else
49             cout<<s<<" is NOT surprising."<<endl;
50     }
51     return 0;
52 }