Openjudge noi 1.13 51: ancient password

【 Topic link 】

OpenJudge NOI 1.13 51: Ancient code

【 Topic test site 】

1. character string

2. Count array

【 Their thinking 】

The original text goes through some kind of “ Alternative method ” After it becomes ciphertext , Each character is converted to a certain character , Different characters get different characters after replacement .
Then the distribution of the number of characters appearing in the original text and the ciphertext must be the same

For example, the original text has two characters 5 Time ,3 Characters appear 2 Time ,4 Characters appear 1 Time . There must be two characters in the ciphertext 5 Time ,3 Characters appear 2 Time ,4 Characters appear once . Although characters with the same number of occurrences are different , But the distribution must be the same .

After replacement , Even if you rearrange , The distribution of the number of character occurrences does not change .
therefore , As long as the distribution of the number of characters in the original text and the ciphertext is the same , Then the original text can be changed into ciphertext through replacement and rearrangement .

example ：
Ciphertext ：JWPUDJSTVP, Character distribution ： There are two characters （JP） appear 2 Time , Yes 6 Characters （WUDSTV） appear 1 Time .
original text ：VICTORIOUS, Character distribution ： There are two characters （IO） appear 2 Time , Yes 6 Characters （VCTRUS） appear 1 Time .
The distribution of occurrence times of original and ciphertext characters is the same , Let the original text and the ciphertext replace each other with the same number of characters （ original text IO Replace with JP, original text VCTRUS Replace with WUDSTV）, Then it is easy to find a position correspondence , Rearrange the characters of a string in a certain order , Get the ciphertext string .

Turn capital letters into numbers , Numbers i For letters i+'A', That is to say 0 Corresponding A,1 Corresponding B,…,25 Corresponding Z.
ct[i] Express i The number of times the corresponding letter appears .
First traverse the string , Count the number of each letter , obtain ct Array .
set up d Array ,d[i] Indicates that... Appears in this string i The number of letters of times .（ such as "AABBCC", appear 2 The letters of times are 2 individual , that d[2] by 3）
Traverse ct Array , obtain d Array .
For the original text and ciphertext , Get... Separately d1,d2 Two arrays . If the two arrays are identical , That is, the distribution of occurrence times of two string characters in the original ciphertext is the same , The original text can be changed into ciphertext . Otherwise, it cannot be changed into ciphertext .

【 Solution code 】

solution 1：

• C style Using arrays , A character array

#include<bits/stdc++.h>
using namespace std;
#define N 105
char s1[N], s2[N];
int d1[N], d2[N];//d1[i]: The first 1 ... appears in a string i The number of letters of times  d2[i]: The first 2 ... appears in a string i The number of letters of times 
void getArrD(char s[], int d[])
{
    
    int len = strlen(s), ct[26] = {
    };
    for(int i = 0; i < len; ++i)
        ct[s[i]-'A']++;
    for(int i = 0; i < 26; ++i)
        d[ct[i]]++;    
} 
int main()
{
    
    scanf("%s\n%s", s1, s2);
    getArrD(s1, d1);
    getArrD(s2, d2);
    for(int i = 1; i <= 100; ++i)// Judge d1 And d2 Is it exactly the same  
    {
    
        if(d1[i] != d2[i])
        {
    
            printf("NO");
            return 0;
        }
    }
    printf("YES");
    return 0;
}

• C++ style Use vector,string

#include<bits/stdc++.h>
using namespace std;
#define N 105
struct Node
{
    
    int t, n;// appear t The letters of times are n individual 
    Node(){
    }
    Node(int a, int b):t(a), n(b){
    }
    bool operator != (Node b)
    {
    
        return t != b.t || n != b.n;
    }
    bool operator < (const Node &b) const// Sort in ascending order of occurrence  
    {
    
        return t < b.t;
    }
};
string s1, s2;
vector<Node> v1, v2;//v1 Save the first 1 How many letters appear in a string several times  v2 Save the first 2 How many letters appear in a string several times  
vector<Node> getVec(string s)
{
    
    vector<Node> v;
    int ct[26] = {
    };
    for(int i = 0; i < s.length(); ++i)
        ct[s[i]-'A']++;
    for(int i = 0; i < 26; ++i)
    {
    
        if(ct[i] > 0)
        {
    
            int j;
            for(j = 0; j < v.size(); ++j)
            {
    
                if(v[j].t == ct[i])
                {
    
                    v[j].n++;
                    break;
                }
            }
            if(j == v.size())// Did not find  
                v.push_back(Node(ct[i], 1));
        }
    }
    return v;
}
int main()
{
    
    cin >> s1 >> s2;
    v1 = getVec(s1);
    v2 = getVec(s2);
    if(v1.size() != v2.size())
        cout << "NO";
    else
    {
    
        sort(v1.begin(), v1.end());// Yes v1 And v2 Sort  
        sort(v2.begin(), v2.end());
        for(int i = 0; i < v1.size(); ++i)// Judge v1 And v2 Is it exactly the same  
        {
    
            if(v1[i] != v2[i])
            {
    
                cout << "NO";
                return 0;
            }
        }
        cout << "YES";
    }
    return 0;
}