c - 换位密码编译太长

Question

我需要编写一个解码换位密码的程序。一开始我有一个词，它是加密文本。 key 的长度等于接收到的字的-1 长度。 key 是随机的。

例子:

1. >

   input text:Uniz isvrh tiesiime ffrmfbi jz tpywjhpf gx ucs zgvey eoj e igpg himua xgxfx qbxo xgw b xihapbx vftx jt xik jpxq pl eo owpygfrit zvjgrhri
   input word: mark
   output:They could scarcely believe it possible at two yards and a half below water mark was a regular rent in the form of an isosceles triangle
   

2. >

   input text:Qr oc cvtmxen ev Rga Asto vlg uwiuxksp acw cx kxu lgmilv
   input word:was
   output:On my arrival at New York the question was at its height
   

3. >

   input text: Rt kolniz qufkbnx R gjvoczkm zqk kgobzkwin ul cnn suwyckx
   input word: effect
   output:In effect however I admitted the existence of the monster
   

对于示例 1 和 2，程序编译速度非常快，但是对于示例 3该程序编译了很长时间，因为我有太多 for 循环。

#include <stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>


int main()
{
    unsigned int i = 0;
    int key[10];
    unsigned int k = 0;
    int check;
    unsigned int j, jj, jjj, jjjj, jjjjj, jjjjjj;
    int n = 50;
    char slowo[10];
    char plain[500], cipher[500];


    fflush(stdin);
    printf("Enter text:");
    fgets(plain, 500, stdin);
    printf("Enter word:");
    fgets(slowo, 500, stdin);

    if (strlen(slowo) == 4)
    {
        for (j = n; j != 0; j--)
        {
            key[0] = (j - 25);
            for (jj = n; jj != 0; jj--)
            {
                key[1] = (jj - 25);
                for (i = 0; i<strlen(plain); i++)
                {
                    if (isalpha(plain[i]))
                    {
                        if (islower(plain[i]))
                        {
                            check = plain[i];

                            if (islower(plain[i]) && check + key[k]>96 && check + key[k]<123)
                            {
                                cipher[i] = (plain[i] + key[k] - 'a') % 26 + 'a';
                            }
                            else
                            {
                                check = 123 + (check - 97 + key[k]);
                                cipher[i] = (check - 'a') % 26 + 'a';
                                check = 0;
                            }
                        }
                        else
                        {
                            check = plain[i];
                            if (isupper(plain[i]) && check + key[k]>64 && check + key[k]<91)
                            {
                                cipher[i] = (plain[i] + key[k] - 'A') % 26 + 'A';
                            }

                            else
                            {
                                check = 91 + (check - 65 + key[k]);
                                cipher[i] = (check - 'A') % 26 + 'A';
                                check = 0;


                            }
                        }
                    }
                    else
                        if (isspace(plain[i]))
                        {
                            k--;


                            cipher[i] = plain[i];
                        }
                    k++;
                    if (k>strlen(slowo) - 3)//ostatniznak + \0
                        k = 0;
                }
                for (i = 0; i<strlen(plain); i++)
                {

                    if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && cipher[i + 3] == slowo[2] && isspace(cipher[i + 4]))
                    {

                        cipher[strlen(plain) - 1] = '\0';
                        printf("%s", cipher);
                        return 0;

                    }
                }

            }
        }
    }

    if (strlen(slowo) == 5)
    {
        for (j = n; j != 0; j--)
        {
            key[0] = (j - 25);

            for (jj = n; jj != 0; jj--)
            {
                key[1] = (jj - 25);

                for (jjj = n; jjj != 0; jjj--)
                {
                    key[2] = (jjj - 25);

                    for (i = 0; i<strlen(plain); i++)
                    {
                        if (isalpha(plain[i]))
                        {
                            if (islower(plain[i]))
                            {
                                check = plain[i];

                                if (islower(plain[i]) && check + key[k]>96 && check + key[k]<123)
                                {
                                    cipher[i] = (plain[i] + key[k] - 'a') % 26 + 'a';
                                }
                                else
                                {
                                    check = 123 + (check - 97 + key[k]);
                                    cipher[i] = (check - 'a') % 26 + 'a';
                                    check = 0;
                                }
                            }
                            else
                            {
                                check = plain[i];
                                if (isupper(plain[i]) && check + key[k]>64 && check + key[k]<91)
                                {
                                    cipher[i] = (plain[i] + key[k] - 'A') % 26 + 'A';
                                }

                                else
                                {
                                    check = 91 + (check - 65 + key[k]);
                                    cipher[i] = (check - 'A') % 26 + 'A';
                                    check = 0;


                                }
                            }
                        }
                        else
                            if (isspace(plain[i]))
                            {
                                k--;


                                cipher[i] = plain[i];
                            }
                        k++;
                        if (k>strlen(slowo) - 3)//ostatniznak + \0
                            k = 0;
                    }
                    for (i = 0; i<strlen(plain); i++)
                    {

                        if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && cipher[i + 3] == slowo[2] && cipher[i + 4] == slowo[3] && isspace(cipher[i + 5]))
                        {
                            cipher[strlen(plain) - 1] = '\0';
                            printf("%s", cipher);
                            return 0;

                        }
                    }
                }
            }
        }
    }
    if (strlen(slowo) == 6)
    {
        for (j = n; j != 0; j--)
        {
            key[0] = (j - 25);

            for (jj = n; jj != 0; jj--)
            {
                key[1] = (jj - 25);
                for (jjj = n; jjj != 0; jjj--)
                {
                    key[2] = (jjj - 25);
                    for (jjjj = n; jjjj != 0; jjjj--)
                    {
                        key[3] = (jjjj - 25);
                        for (i = 0; i<strlen(plain); i++)
                        {
                            if (isalpha(plain[i]))
                            {
                                if (islower(plain[i]))
                                {
                                    check = plain[i];

                                    if (islower(plain[i]) && check + key[k]>96 && check + key[k]<123)
                                    {
                                        cipher[i] = (plain[i] + key[k] - 'a') % 26 + 'a';
                                    }
                                    else
                                    {
                                        check = 123 + (check - 97 + key[k]);
                                        cipher[i] = (check - 'a') % 26 + 'a';
                                        check = 0;
                                    }
                                }
                                else
                                {
                                    check = plain[i];
                                    if (isupper(plain[i]) && check + key[k]>64 && check + key[k]<91)
                                    {
                                        cipher[i] = (plain[i] + key[k] - 'A') % 26 + 'A';
                                    }

                                    else
                                    {
                                        check = 91 + (check - 65 + key[k]);
                                        cipher[i] = (check - 'A') % 26 + 'A';
                                        check = 0;


                                    }
                                }
                            }
                            else
                                if (isspace(plain[i]))
                                {
                                    k--;


                                    cipher[i] = plain[i];
                                }
                            k++;
                            if (k>strlen(slowo) - 3)//ostatniznak + \0
                                k = 0;
                        }
                        for (i = 0; i<strlen(plain); i++)
                        {

                            if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && cipher[i + 3] == slowo[2] && cipher[i + 4] == slowo[3] && cipher[i + 5] == slowo[4] && isspace(cipher[i + 6]))
                            {
                                cipher[strlen(plain) - 1] = '\0';
                                printf("%s", cipher);
                                return 0;

                            }
                        }
                    }

                }
            }

        }
    }
    if (strlen(slowo) == 7)
    {
        for (j = n; j != 0; j--)
        {
            key[0] = (j - 25);
            for (jj = n; jj != 0; jj--)
            {
                key[1] = (jj - 25);
                if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && isspace(cipher[i + 7]))
                {
                    jj--;
                }

                for (jjj = n; jjj != 0; jjj--)
                {
                    key[2] = (jjj - 25);

                    for (jjjj = n; jjjj != 0; jjjj--)
                    {
                        key[3] = (jjjj - 25);


                        for (jjjjj = n; jjjjj != 0; jjjjj--)
                        {
                            key[4] = (jjjjj - 25);

                            for (i = 0; i<strlen(plain); i++)
                            {
                                if (isalpha(plain[i]))
                                {
                                    if (islower(plain[i]))
                                    {
                                        check = plain[i];

                                        if (islower(plain[i]) && check + key[k]>96 && check + key[k]<123)
                                        {
                                            cipher[i] = (plain[i] + key[k] - 'a') % 26 + 'a';
                                        }
                                        else
                                        {
                                            check = 123 + (check - 97 + key[k]);
                                            cipher[i] = (check - 'a') % 26 + 'a';
                                            check = 0;
                                        }
                                    }
                                    else
                                    {
                                        check = plain[i];
                                        if (isupper(plain[i]) && check + key[k]>64 && check + key[k]<91)
                                        {
                                            cipher[i] = (plain[i] + key[k] - 'A') % 26 + 'A';
                                        }

                                        else
                                        {
                                            check = 91 + (check - 65 + key[k]);
                                            cipher[i] = (check - 'A') % 26 + 'A';
                                            check = 0;


                                        }
                                    }
                                }
                                else
                                    if (isspace(plain[i]))
                                    {
                                        k--;


                                        cipher[i] = plain[i];
                                    }
                                k++;
                                if (k>strlen(slowo) - 3)//ostatniznak + \0
                                    k = 0;
                            }
                            for (i = 0; i<strlen(plain); i++)
                            {

                                if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && cipher[i + 3] == slowo[2] && cipher[i + 4] == slowo[3] && cipher[i + 5] == slowo[4] && cipher[i + 6] == slowo[5] && isspace(cipher[i + 7]))
                                {
                                    cipher[strlen(plain) - 1] = '\0';
                                    printf("%s", cipher);
                                    return 0;

                                }
                            }
                        }
                    }
                }
            }
        }
    }
    if (strlen(slowo) == 8)
    {
        for (j = n; j != 0; j--)
        {
            key[0] = (j - 25);
            for (jj = n; jj != 0; jj--)
            {
                key[1] = (jj - 25);

                for (jjj = n; jjj != 0; jjj--)
                {
                    key[2] = (jjj - 25);
                    for (jjjj = n; jjjj != 0; jjjj--)
                    {
                        key[3] = (jjjj - 25);


                        for (jjjjj = n; jjjjj != 0; jjjjj--)
                        {

                            key[4] = (jjjjj - 25);

                            for (jjjjjj = 0; jjjjjj != 0; jjjjjj--)
                            {
                                key[5] = (jjjjjj - 25);
                                for (i = 0; i<strlen(plain); i++)
                                {
                                    if (isalpha(plain[i]))
                                    {
                                        if (islower(plain[i]))
                                        {
                                            check = plain[i];

                                            if (islower(plain[i]) && check + key[k]>96 && check + key[k]<123)
                                            {
                                                cipher[i] = (plain[i] + key[k] - 'a') % 26 + 'a';
                                            }
                                            else
                                            {
                                                check = 123 + (check - 97 + key[k]);
                                                cipher[i] = (check - 'a') % 26 + 'a';
                                                check = 0;
                                            }
                                        }
                                        else
                                        {
                                            check = plain[i];
                                            if (isupper(plain[i]) && check + key[k]>64 && check + key[k]<91)
                                            {
                                                cipher[i] = (plain[i] + key[k] - 'A') % 26 + 'A';
                                            }

                                            else
                                            {
                                                check = 91 + (check - 65 + key[k]);
                                                cipher[i] = (check - 'A') % 26 + 'A';
                                                check = 0;


                                            }
                                        }
                                    }
                                    else
                                        if (isspace(plain[i]))
                                        {
                                            k--;


                                            cipher[i] = plain[i];
                                        }
                                    k++;
                                    if (k>strlen(slowo) - 3)//ostatniznak + \0
                                        k = 0;
                                }
                                for (i = 0; i<strlen(plain); i++)
                                {

                                    if (isspace(cipher[i]) && cipher[i + 1] == slowo[0] && cipher[i + 2] == slowo[1] && cipher[i + 3] == slowo[2] && cipher[i + 4] == slowo[3] && cipher[i + 5] == slowo[4] && cipher[i + 6] == slowo[5] && cipher[i + 7] == slowo[6] && isspace(cipher[i + 7]))
                                    {
                                        cipher[strlen(plain) - 1] = '\0';
                                        printf("%s", cipher);
                                        return 0;

                                    }
                                }
                            }
                        }
                    }

                }
            }
        }
    }
    else {
        printf("Error");
        return 1;
    }
}

我想优化代码以使其更快，但我不知道。

Answer 1

您的代码中有一些可能的优化 - 所谓的锁孔优化，但我宁愿更改您正在使用的算法。锁孔优化是小菜一碟，而且premature optimization is the root of all evil . 降低算法的复杂性几乎总是您的首要任务。然后，也只有到那时，您才能进行进一步的优化。

这里您知道 key 长度是(在第三个示例中)五，因为 crib effect 是六个字符；我们将 key 称为 12345。

我们将 key 与密文对齐，因为忽略了空格:

12 345123 4512345 1 23451234 512 345123451 23 451 2345123
Rt kolniz qufkbnx R gjvoczkm zqk kgobzkwin ul cnn suwyckx

我们可以现在在 O(n³) 中实现暴力巴贝奇解密使用线性方程系统:

x1 - 1 = R
x2 - 2 = t
x3 - 3 = k
x4 - 4 = o
x5 - 5 = l
x6 - 1 = n
...
x48 - 3 = x

但我们可以观察到我们只有一个词，其长度等于“effect”的长度 - 它是“kolniz”。 这意味着我们可以立即恢复 key :这就是“nikol - efeec”的区别。第一个符号 1 等于从 effect 的第二个 e 向前移动到 kolniz 的 n ，即9个位置。因此，当我们找到映射到 worm 的第一个符号的字母时，例如第一个“R”，我们从 R 返回 9 个位置，找到“I”。

上述算法大致为 O(n+m)，其中 n 是密文的长度，m 是 key 的长度。

假设我们有两个长度等于“effect”的单词，假设它们是“abcdef”和“ghijkl”。我们使用哪一个？

假设1:abcdef是effect的密文。如果这是真的，那么 'e' 的第一个符号的移位是 'a' 并且相同的移位必须将 'f' 变成 't'。

假设2:ghikl是effect的密文。如果这是真的，那么“e”的第一个符号的移位是“g”，相同的移位必须将“l”变成“t”。

两个假设都为真而我们无法确定哪个假设正确的概率是另一个词的第一个和最后一个字母具有与“e”和“t”相同的移位差异的概率' 例如，在我们的婴儿床中，第一个词是“效果”，另一个是“美洲狮”、“挽歌”、“哈洛”或“老爷车”。这些机会很少。