hihoCoder 1709 凯撒密码 字符串相似

算法 hihoCoder

刷算法题刷到怀疑智商，人丑就要多读书，没办法，多记录多总结多积累，谁让咱笨呢，呜呜呜～～～

2018-03-18[Offer收割]编程练习赛51的B题

描述

恺撒密码是一种古老的加密方法。它将26个英文字母'A'-'Z'向左循环移动K位，得到新的密码表。

例如K=2，有:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
CDEFGHIJKLMNOPQRSTUVWXYZAB

则用'C'替代'A'，'D'替代'B'……
对于两个只包含大写字母的字符串A和B，如果A和B长度相同，并且A可以通过某种(某个K)恺撒加密得到B，我们就认为A和B是相似的。
例如"ABC"与"DEF"相似，"HI"与"ZA"相似。显然"相似"关系具有传递性和对称性。
给定N个字符串，请你将相似的字符串聚成一类，并输出最终有几个不同的类别。

分析

按照密码表的意思，字符的加密方法很简单，给两个字符，$k$的值为

int get_K(char a, char b){
    return (b - a + 26) % 26;
}

题目里面明确说了，“相似”关系具有传递性和对称性，所以我第一时间想到的一个方法是每类相似的字符串均用第一个出现的作为代表，用一个vector<string>保存，每次来一个串就和vector<string>中的所有字符比较相似性，存在相似的继续下一个，不存在把其加到列表里面

这里比较相似性的时候，字符串A与字符串B相似，那么其每一对字符的左移位数应该相同，求相似

bool similar(string a, string b){
    if(a.size() != b.size())
        return false;
    else{
        int k = get_K(a[0], b[0]);
        if(k<0){
            return false;
        }else{
            for(int i=1; i<a.size(); i++){
                if(k!=get_K(a[i], b[i])){
                    return false;
                }
            }
            return true;
        }
    }
}

vector<string> A;
int main(){
    int N;
    scanf("%d", &N);
    string s;
    for(int i=0; i<N; i++){
        cin>>s;
        if(A.size()==0){
            A.push_back(s);
        }else{
            int existed = false;
            for(int i=0; i<A.size(); i++){
                if(similar(A[i], s)){
                    existed = true;
                    break;
                }
            }
            if(!existed){
                A.push_back(s);
            }
        }
    }
    cout<<A.size()<<endl;
}

这样写很显然的就超时了

正确思路

上面超时的原因是少想了一步，上面的超时的原因在比较字符串相似性这一步，由于相似的字符串都可以相互转换，所以可以用一个“代表”表示这一整套相似字符串（上面超时的也是这个思路），这样我们不直接比较相似了，而是把其都转换为一个相同的字符串，并且每一对相似字符串的左移位数是相同的，故一个字符串转换为另一个相似字符串只需要知道左移位数$k$即可，而且这对字符串中的对应的每一对字符的左移位数均为$k$

这样一来，我们只需要把字符串的第一个字符设为'A'，根据第一个字符与'A'求出$k$，那么后面的字符的对应字符也就唯一确定了，这样也就达到了把相似字符串转换为“唯一代表”的目的，也就是说相似的字符串得到的编码字符是相同的，然后把它们转换完插入到一个set<string>，最后输出这个集合的大小就完事了

#include <iostream>
#include <set>
using namespace std;
int get_K(char a, char b){
    return (b - a + 26) % 26;
}
set<string> S;
int main(){
    int N;
    cin>>N;
    string s;
    int k;
    for(int i=0; i<N; i++){
        cin>>s;
        k = get_K(s[0], 'A');
        s[0] = 'A';
        for(int j=1; j<s.size(); j++){
            s[j] = 'A' + (s[j] + k) % 26;
        }
        S.insert(s);
    }
    cout<<S.size()<<endl;
}