【题解】playfair

题意

给你一个字符串通过以下方式加密输出

1. 通过密钥制作字母表，首先将密钥字符中的所有j替换成i，在将重复出现过的字符除去得到一个新的没有重复字符出现的new_key。通过new_key来制作密码表，先按顺序将密钥放入密码表中，并开一个vis数组来记录出现的字母，接着处理未出现过的。用一个变量w来表示未出现过的，若字母在vis中出现过则w++，然后可以对字母表赋值。
2. 先将明文中的j都重新赋值为i，接着我们每次处理两个字符。若两个字符是相同的直接加入ans串。接着我们在密码表中来定位两个字母的位置，当然可以用map+pair来优化查表。
3. 若两个字母在同一行则加密字母分别为其紧挨的右边字母，最后一列的右边为第一列，可以用Matrix[x1][(y1+1)%5]来表示
4. 若两个字母在同一列则加密字母分别为其紧挨的下边字母，最后一行的下边为第一行，可以用ans+=Matrix[(x1+1)%5][y1];来表示
5. 不同行不同列的字母，加密字母分别为所构成矩形的同行对角字母，可以用Matrix[x1][y2]和Matrix[x2][y1]表示对应的字母。
6. 若该字符串长度为奇数则最后一个字母不做处理直接加入ans串中

   思路

   根据题意进行模拟既可以，注意替换j为i，处理字符串奇数长度模拟正确即可AC，复杂度为O(|str|*25)

   代码

   void CreateMatrix(string key,char Matrix[5][5])
   {
    bool vis[26]= {0};
    string new_key="";
    for(int i=0;i<key.length();i++)
    {
        if(key[i]=='j')
            key[i]='i';
        if(vis[key[i]-'a']==0)
            {
                vis[key[i]-'a']=1;
                new_key+=key[i];
            }
    }
    key=new_key;
    memset(vis,0,sizeof(vis));
    vis['j'-'a']=1;
    int s=0;
    int w=0;
    for(int i=0; i<5; i++)
        for(int j=0; j<5; j++)
        {
            if(s<key.length())
            {
                Matrix[i][j]=key[s];
                vis[key[s]-'a']=1;
                s++;
            }
            else
            {
                while(vis[w]==1) w++;
                Matrix[i][j]='a'+w;
                vis[w]=1;
                w++;
            }
        }
   }
   string solve(string str,char Matrix[5][5])
   {
    for(int i=0;i<str.length();i++)
        if(str[i]=='j')
            str[i]='i';
    string ans="";
    for(int i=0;i<str.length();i+=2)
    {
        if(i==str.length()-1)
            break;
        if(str[i]==str[i+1])
        {
            ans+=str[i];
            ans+=str[i+1];
            continue;
        }
        int x1,y1,x2,y2;
        for(int j=0; j<5; j++)
            for(int k=0; k<5; k++)
                if(Matrix[j][k]==str[i])
                {
                    x1=j;
                    y1=k;
                }
                else if(Matrix[j][k]==str[i+1])
                {
                    x2=j;
                    y2=k;
                }
        if(x1==x2)
        {
            ans+=Matrix[x1][(y1+1)%5];
            ans+=Matrix[x2][(y2+1)%5];
        }
        else if(y1==y2)
        {
            ans+=Matrix[(x1+1)%5][y1];
            ans+=Matrix[(x2+1)%5][y2];
        }
        else
        {
            ans+=Matrix[x1][y2];
            ans+=Matrix[x2][y1];
        }
    }
    if(str.length()%2==1)
        ans+=str[str.length()-1];
    return ans;
   }
   class Solution {
   public:
    /**
     * playfair加密算法
     * @param key string字符串 密钥
     * @param str string字符串 明文
     * @return string字符串
     */
    string Encode(string key, string str) {
        // write code here
        char Matrix[5][5];
        CreateMatrix(key,Matrix);
        return solve(str,Matrix);
    }
   };