生成與集合中不匹配的字符串

奇怪的問題的排序 - 我將如何去生成一個字符串，它不匹配任何字符串中的任何字符串？我不想對字符串做任何假設。解決方案是基於理想的STL，但並不一定是生成與集合中不匹配的字符串

例子：

vector<string> strings; 
/*...*/ 
string unMatching = generateUnmatching(strings); //this is the function I want 

assert(find(strings.begin(), strings.end(), unMatching) == strings.end());

來源

2012-03-03 Lucretiel

爲什麼這聽起來像家庭作業懷疑？ – 2012-03-03 05:47:11

我保證它不是，但對於我的生活，我不記得我爲什麼問這個 – Lucretiel 2012-06-18 01:38:25

一種方法是使用diagonalization：

開始與空字符串s。
看看集合中第一個字符串的第一個字符。選擇除此之外的任何字符，並將其附加到s。
看看集合中第二個字符串的第二個字符。選擇除此之外的任何字符，並將其附加到s。
遵循相同模式，始終查看第i個字符串的第i個字符並向s添加不同的字符。
當您完成了集合中的最後一個字符串後，s將與集合中的每個字符串在至少一個位置上不同。

另一種方法是複製集合中最長的字符串並將任何字符附加到副本。這個新的字符串將不同於集合中的每個字符串。

還有各種各樣的其他方式來完成同樣的事情。給問題添加一些約束將有助於選擇對您的問題最有意義的算法。例如，您可能決定生成最短的字符串，該字符串與集合中的任何字符串不匹配，或者具有最低字典排序值的字符串，或與其他字符串具有最小字符數量的字符串最短的字符串或...

來源

2012-03-03 05:55:02 Caleb

這不是假定集合中的所有字符串都有特定的長度嗎？（例如，如果第6個字符串的長度是2，那該怎麼辦？） – 2012-03-03 06:00:45

@JamesBedford不是。如果第i個字符串的長度小於i，則可以自由選擇任何字符。如果第6個字符串的長度爲2，那麼將任何字符放在s的第6個位置使其與該字符串不同。 – Caleb 2012-03-03 06:09:18

不，任何字符都不同於缺少（字符串結尾）字符，因此只需使用任何（「a」）。 – 2012-03-03 06:09:52

你可以使用一個隨機數發生器（下面的例子），我覺得ASCII可打印字符在33開始，在127結束，從-1到-95

#include <stdlib.h> 
#include <stdio.h> //only for printf 
#define RANDINT(r) ((int)(r * (float)random() /(float)RAND_MAX + 0.5)) 
#define OFFSETRANDINT(r,o) (RANDINT(r) + o) 
#define RANDINTX2Y(x,y) (OFFSETRANDINT((y-x),x)) 

int main(){ 
    srandom(time(NULL)); // important to call this first, but only once 
    printf("%d\n",RANDINT(2147483647)); //a random int between 0 and 2147483647 
    printf("%d\n",OFFSETRANDINT(10,10)); //starting @ 10 with a range of 10 (10-20) 
    printf("%d\n",RANDINTX2Y(0,10)); //between 0 and 10 
}

你可能需要轉換INT到（字符），以便您可以將其存儲在一個字符串中

然後您可以使用strstr或strcasestr，具體取決於是否大小寫只是strcat每個字符串到「乾草堆」，如果它返回！ TRUE

#include <string.h> 
char *strstr(const char *haystack, const char *needle); 
char *strcasestr(const char *haystack, const char *needle);

來源

2012-03-03 06:11:55 technosaurus

你可以使用一個UUID發電機，就像從提振之一：

#include <boost/uuid/uuid.hpp> 
#include <boost/uuid/uuid_io.hpp> 
#include <boost/uuid/uuid_generators.hpp>  

int main() 
{ 
    using namespace boost::uuids; 
    random_generator gen; 
    uuid u = gen(); 
    std::string s = to_string(u); 
    std::cout << s; 
}

來源

2012-03-03 06:15:25

如果你真的沒有關於結果字符串的任何要求，你可以簡單地做：

string answer = "a"; 
while (find(strings.begin(), strings.end(), unMatching) != strings.end()) 
    answer += "a";

顯然它似乎並不是你想要的。

這裏的優化解決方案，幫助你找到在最短的時間內量儘可能短的答案：

建立與您的字符集trie。
從根節點進行廣度優先搜索，遇到的第一個空節點將是最短的答案。

優化實現的時間複雜度爲O（number_of_characters_in_all_strings），而向量循環和查找的簡單實現爲O（number_of_strings * lenth_of_string）。

來源

2012-03-03 06:27:15 myin528

生成與集合中不匹配的字符串

回答

相關問題