檢查字元串是否為英語解密的相對快速的方法是什麼？

我在 Stack Overflow 上問過這個問題，但有人告訴我在這裡問。

我正在編寫一個程序來解密使用 Vigenere 密碼加密的文本。到目前為止它工作得很好，但我目前的問題是我需要一種有效的方法來檢查字元串是否被解密。到目前為止，我一直在檢查字元串包含一組最常見的英語單詞的次數，但如果字元串沒有空格，那將不起作用。

例如，以下“明文”：

XPAWWALLTPJZYYZWBGSHGARECPVHDAAPLJLBGAPVTFVCWAS

包含“all”、“are”、“was”和“as”，但顯然沒有解密。

檢查字元串是否被解密的好方法是什麼？

在 purley 中搜尋字元串中的子字元串將是一個程式問題，但由於 Stackoverflow 已經將您發送到這裡，我將嘗試一下：

爪哇：

public class MyClass
{
   public static void main(String[] args)
   {
       String myString = "XPAWWALLTPJZYYZWBGSHGARECPVHDAAPLJLBGAPVTFVCWAS";

       int intIndex = myString.indexOf("ARE");

       if(intIndex == - 1)
       {
           System.out.println("ARE was not found");
       }
       else
       {
           System.out.println("Found ARE at index "+ intIndex);
       }
   }
}

C＃：

using System;

public class MyClass
{
  public static void Main()
  {
     string myString = "XPAWWALLTPJZYYZWBGSHGARECPVHDAAPLJLBGAPVTFVCWAS";

     if (myString.Contains("ARE") == true)
     {
        Console.WriteLine("Found ARE");
     }
     else
     {
        Console.WriteLine("Word ARE was not found!");
     }
  }
}

這些都應該有效。

然後，您可以創建一個循環，在字元串中搜尋常用詞。

這純粹是一個算法問題——給定一些字元串 $ s := s_1s_2\dots s_n $ （在哪裡 $ s_i\in\Sigma $ ，一些字母表）和一些單詞集合 $ W_1,\dots, W_j \in \Sigma^* $ , 想解析 $ s $ 連接一些連續的單詞。

這有一個自然的動態程式解決方案，這可能會非常有效。主要問題是檢查某些字元串是否在您的單詞集合中的效率，但我想有字典 API 可以有效地發生這種情況。

具體來說，動態規劃方案建構一個數組 $ T $ ， 在哪裡 $ T[i] $ 將以某種方式（稍後描述）編碼所有有效的解析 $ s_i\dots s_n $ 成英文單詞。請注意，如果有 $ T[j] $ 為所有人填寫 $ j > i $ ，應該很容易計算 $ T[i] $ 本身—-檢查是否 $ s_i\dots s_{j-1} $ 對所有人都是有效的詞 $ j > i $ . 無論何時，添加 $ s_i\dots s_{j-1} + T[j] $ 至 $ T[i] $ . 我的意思是設置 $ T[i] = \cup_{w\in T[j]} s_i \dots s_{j-1} + w $ 在哪裡 $ w $ 是到目前為止已經解析的句子，並且 $ s_i\dots s_{j-1} + w $ 表示連接（由空格分隔）。

這將導致 $ T[1] $ 包含您的句子的所有可能解析為英語單詞，如果您想檢查它們是否在語法上正確（例如），這將很有用。不過，這可能是太多的資訊——也許你想完全忽略語法，只關心是否存在這樣的解析。一個人可以節省記憶體，然後只儲存在 $ T[i] $ 指數 $ j $ 這樣 $ s_i\dots s_{j-1} $ 是一個有效的詞。然後可以通過查看是否存在路徑來檢查是否存在有效的解析 $ T[1] $ 至 $ T[n] $ 在有頂點的圖中 $ {1,\dots, n} $ , 和邊緣 $ i\to j $ 每當 $ j\in T[i] $ . 這樣的路徑 $ 1\to i_1\to i_2\to\dots \to i_k \to n $ 可以理解為破 $ s $ 成詞 $ s_1\dots s_{i_1-1}, s_{i_1}\dots s_{i_2-1},\dots, s_{i_k}\dots s_n $ , 這些都是有效的詞 $ T $ .

在這個減少記憶體版本的問題中，填寫每個 $ T[i] $ 需要 $ O(nA) $ 時間，地點 $ A $ 是檢查字元串是否在您的單詞集合中所需的時間。填寫整個表格然後需要 $ O(n^2A) $ 時間。查找路徑是否存在 $ T[1] $ 至 $ T[n] $ 然後可以通過多種方式完成 — 請注意，路徑甚至不需要是最短路徑，這使問題變得更容易（並且可以只使用 BFS/DFS，最多添加 $ O(n^2) $ 問題）。

引用自：https://crypto.stackexchange.com/questions/78441