秒懂算法 | 字符串匹配算法实例分析之潜伏者、最低三元字符串

小咪咪 2024-02-23 07:37 12阅读 0赞

![d1d915b89e0a4554a56b97f42d8fd8bc.png][]

字符串匹配算法在实际工程中经常遇到，是各大公司笔试、面试的常考题目。此算法通常输入为原字符串（string）和子串（pattern），要求返回子串在原字符串中首次出现的位置。比如原字符串为“ABCDEFG”，子串为“DEF”，则算法返回3。常见的算法包括BF（Brute Force，暴力检索）、RK（Robin-Karp，哈希检索）、KMP（教科书上最常见的算法）、BM（Boyer Moore）、Sunday等。

01、**实例分析：潜伏者**

**问题描述:**

R国和 S 国正陷入战火之中，双方都互派潜伏者（间谍），潜入对方内部，伺机行动。历尽艰险后，潜伏于 S 国的 R 国间谍小 C 终于摸清了 S 国军用密码的编码规则:

(1) S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所得的内容均由大写字母‘A’～‘Z’构成（无空格等其他字符）。

(2) S 国对每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替换为其对应的“密字”。

(3) 每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。“密字”可以和原字母相同。

例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则原信息“ABA”被加密为“ACA”。

现在，小 C 通过内线掌握了 S 国网络上发送的一条加密信息及其对应的原信息。小 C希望能通过这条信息破译S国的军用密码。小C的破译过程是这样的: 扫描原信息，对于原信息中的字母X（代表任一大写字母），找到其在加密信息中的对应大写字母Y，并认为在密码里Y是X的密字。如此进行下去，直到停止于如下的某个状态:

(1) 所有信息扫描完毕，‘A’～‘Z’所有26个字母在原信息中均出现过并获得了相应的“密字”。

(2) 所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。

(3) 扫描中发现掌握的信息里有明显的自相矛盾或错误（违反 S 国密码的编码规则）。例如，某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。

在小 C 忙得头昏脑涨之际，R 国司令部又发来电报，要求他翻译另外一条从 S 国刚刚截取到的加密信息。现在请你帮助小 C: 通过内线掌握的信息尝试破译密码，然后利用破译的密码翻译电报中的加密信息。

**输入格式:**

共3行，每行为一个长度在1～100的字符串。

第1行为小C掌握的一条加密信息。

第2行为第1行的加密信息所对应的原信息。

第3行为R国司令部要求小C翻译的加密信息。

输入数据保证所有字符串仅由大写字母‘A’～‘Z’构成，且第1行长度与第2行长度相等。

**输出格式:**

共1行。

若破译密码停止时出现（2）和(3)两种情况，则输出Failed（首字母大写，其他小写），否则输出利用密码翻译电报中加密信息后得到的原信息。

**输入样例\#1:**

![394c67c54ecc4a31b45e693d8ceb3c84.png][]

**输出样例:**

![8bcdfbc4d79140aabd73f0a64f1bb9b2.png][]

**输入样例:**

![b4eae416fa7c41829340d7b83578cca3.png][]

**输出样例:**

![308ab9485567468386794d53a786bb39.png][]

**输入样例:**

![6dcaeb3848eb447cba71adec7bcf4ee3.png][]

**输出样例:**

![acda5524351a46e8a7669f63f034cdbc.png][]

**输入输出样例1说明:**

原信息中的字母‘A’和‘B’对应相同的密字，输出Failed。

**输入输出样例2说明:**

字母‘Z’在原信息中没有出现，输出Failed。

**思路:**

(1) A～Z必须都存在，否则输出Failed。

(2) 密文中的每个字母不能给多个字母使用，否则输出Failed。

**参考程序:**

#include<iostream>
    #include<cstring>
    using namespace std;
    char map[26];
    int main()
    {
    string secret,original,translation;
    int len1,len3;
    int i,j;
    cin>>secret>>original>>translation; ;//输人密文、原文、要翻译的文字
    len1=secret.length() ;  //计算密文长度
    len3=translation.length(); //计算要翻译的文字长度
    if(len1<26)  //若密文长度小于 26 个字母的长度，则不合要求,输出 Eailed,终止程序
    }
    {
    cout<<"Failed"<<endl;
    return 0;
    }
    for(i=0;i<lenl;i++)
    {
    for(j=0;j<i;j++)
    if(original[i]==original[jl&&secret[il!=secret[j]) //若原文中有相同字母,但密文中对应字母不相同,则不合要求,输出 Eailed,终止
    //程序
    {
    cout<<"Failed"<<endl;
    return 0;
    }
    map[secret[il-'A']=original[i];   //存储密文对应的原文 
    }
    for(i=0;i<len3;i++)  //输出翻译后的文字
    cout<<map[translation[i]-'A'];
    cout<<end1;
    return 0;    
    }

## 02、**实例分析：最低三元字符串** ##

**问题描述:**

给定一个三元字符串(该字符串仅由字符'0'、'1'和'2'组成)。

可以交换任意两个相邻(连续)字符'0'和'1'(即将"01"替换为"10"，反之亦然) 或任何两个相邻(连续)字符“1”及“2”(即将“12”替换为“21”，反之亦然)。例如，对于字符串“010210”，可以执行以下步骤。

“010210”→→ “100210”;

“010210” →→ “001210”;

“010210” →→ “010120”;

“010210” →→ “010201”。

例如，对于字符串“010210”，可以执行以下操作: 注意不能将“02”转换为“20”，反之亦然。除上面描述的以外，不能使用给定字符串执行其他任何操作。

你的任务是通过使用这些交换任意次数(可能为零)获得可能的最小值(字典上的)字符串。

如果存在位置i(1≤i≤|a|，其中|s|是字符串"ss"的长度)，则字符串"aa"在字典上小于字符串"bb"(如果字符串"aa"和"bb"有相同的长度)，使得对于每一个j<i< span="">，都有aj=bj, ai<bi< span="">。

**输入:**

输入的第一行包含仅由'0'、'1'和'2'组成的字符串"s"，其长度为1～105(含105)。

**输出:**

打印一个字符串——通过使用上面描述的交换可以获得的最小字符串(字典上的)次数(可能为零)。

**输入样例:**

100210

**输出样例:**

001120

**输入样例:**

11222121

**输出样例:**

11112222

**输入样例:**

**输出样例:**

题意: 给出一串只有0、1、2的数串，其中，0与1可互相交换，1与2可互相交换，求交换后最小的值。

思路: 无论1在哪，总能被换到2的前面，但0无法换到2的前面，因此先统计第一个2前面0的个数，输出；然后再统计整个数串中1的个数，输出；最后再将第一个2后面的所有数字去掉1后输出。

**参考程序:**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    # include< cmath>
    #include<algorithm>
    #include<string>
    # include<cstdlib>
    # include<queue>
    # include< set>
    # include<map>
    #include<stack>
    #include<ctime>
    #include<vector>
    #define INF Ox3f3f3f3f
    # define PI acos(-1.0)
    #define N 1001
    #define MOD 10007
    #define E 1e-6
    # define LL long long
    using namespace std;
    int main()
    {
    string str;
    cin>>str;
    LL len=str.length() ;
    LI num 1=0;
    bool flag=true;
    for(LL i=0;i<len;i++)
    if(str[il=='1')num 1++;
    if(str[i]=='1' str[i]=='2')
    flag=false;
    LL pos;
    LI num 0=0;
    for(LL i=0;i<len;i++)
    f(str[i]=='0')
    num 0++;
    if(str[i]=='2')
    pos=i;
    break;
    if(flag)
    cout<<str<<endl;
    return 0;
    }
    while(num 0--)
    cout<<'0';
    while(num 1--)
    cout<<'1';
    for(LL i=pos;i<len;i++)
    {
    if(str[il=='1')
    continue;
    else
    cout<<str[i];
    }
    cout<<endl;
    return 0;
    }

[d1d915b89e0a4554a56b97f42d8fd8bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/23/ba6fc990602e465486d898e7cc91a1e0.png
[394c67c54ecc4a31b45e693d8ceb3c84.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/23/a170f59b73e2417f836686b68097fc39.png
[8bcdfbc4d79140aabd73f0a64f1bb9b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/23/98ca71ba3a4f4a81bf8386104e912cdd.png
[b4eae416fa7c41829340d7b83578cca3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/23/31abe5c7bd0f4e848e28b6193cdbcc71.png
[308ab9485567468386794d53a786bb39.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/23/a7f10a1b2b194bc2b15f2d31d8aeded2.png
[6dcaeb3848eb447cba71adec7bcf4ee3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/23/39d8b7bdace84fe28ebfb93f31fc2055.png
[acda5524351a46e8a7669f63f034cdbc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/23/01029dd6037945a98f46ab579f5a41cf.png