Tách chuỗi thành các từ

Question

Tôi đang tìm thuật toán hiệu quả nhất để tạo thành tất cả các kết hợp từ có thể có từ một chuỗi. Ví dụ:

Input String: forevercarrot 

Output: 

forever carrot 
forever car rot 
for ever carrot 
for ever car rot 

(Tất cả các từ phải từ từ điển).

Tôi có thể nghĩ đến phương pháp tiếp cận vũ phu. (tìm tất cả các chất nền có thể và phù hợp) nhưng những gì sẽ là cách tốt hơn?

Answer 1

Triển khai psuedocode, khai thác thực tế là mọi phần của chuỗi cần phải là một từ, chúng tôi không thể bỏ qua bất kỳ thứ gì. Chúng tôi làm việc chuyển tiếp từ đầu chuỗi cho đến khi bit đầu tiên là một từ và sau đó tạo tất cả các kết hợp có thể có của phần còn lại của chuỗi. Một khi chúng tôi đã làm điều đó, chúng tôi tiếp tục đi cho đến khi chúng tôi tìm thấy bất kỳ khả năng khác cho từ đầu tiên, và như vậy.

allPossibleWords(string s, int startPosition) { 
    list ret 
    for i in startPosition..s'length 
     if isWord(s[startPosition, i]) 
      ret += s[startPostion, i] * allPossibleWords(s, i) 
    return ret  
} 

Các Bugbear trong mã này là bạn sẽ kết thúc lặp đi lặp lại các phép tính - trong ví dụ của bạn, bạn sẽ kết thúc phải tính toán allPossibleWords("carrot") hai lần - một lần trong ["forever", allPossibleWords["carrot"]] và một lần trong ["for", "ever", allPossibleWords["carrot"]]. Vì vậy, ghi nhớ điều này là một cái gì đó để xem xét.

Answer 2

Sử dụng prefix tree để biết danh sách các từ đã biết. Có lẽ libs như myspell đã làm như vậy. Hãy thử sử dụng sẵn sàng.

Khi bạn tìm thấy kết quả phù hợp (ví dụ: 'xe hơi'), hãy chia tính toán của bạn: một chi nhánh bắt đầu tìm từ mới ('thối'), một nhánh khác tiếp tục khám phá các biến thể của bắt đầu hiện tại ('carrot').

Có hiệu quả bạn duy trì một hàng đợi các cặp (start_position, current_position) số lần dời vào chuỗi của bạn mỗi khi bạn chia tính toán. Một số chủ đề có thể bật từ hàng đợi này song song và cố gắng tiếp tục một từ bắt đầu từ start_position và đã được biết đến là current_position của cặp, nhưng không kết thúc ở đó. Khi một từ được tìm thấy, nó được báo cáo và một cặp khác xuất hiện từ hàng đợi. Khi không thể, không có kết quả nào được tạo ra. Khi phân chia xảy ra, một cặp mới sẽ được thêm vào cuối hàng đợi. Ban đầu, hàng đợi chứa (0,0).

Answer 3

Xem câu hỏi này có câu trả lời hay hơn. Đó là một vấn đề lập trình động tiêu chuẩn:

How to split a string into words. Ex: "stringintowords" -> "String Into Words"?

Answer 4

Chuỗi Input: forevercarrot

Output

:

mãi mãi cà rốt mãi mãi xe thối mãi mãi cà rốt cho xe thối bao giờ

chương trình :

#include<iostream> 
#include<string> 
#include<vector> 
#include<string.h> 
void strsplit(std::string str) 
{ 
    int len=0,i,x,y,j,k; 
    len = str.size(); 
    std::string s1,s2,s3,s4,s5,s6,s7; 
    char *c = new char[len+1](); 
    char *b = new char[len+1](); 
    char *d = new char[len+1](); 
    for(i =0 ;i< len-1;i++) 
    { 
     std::cout<<"\n"; 
     for(j=0;j<=i;j++) 
     { 
      c[j] = str[j]; 
      b[j] = str[j]; 
      s3 += c[j]; 
      y = j+1; 
     } 
     for(int h=i+1;h<len;h++){ 
      s5 += str[h]; 
     } 
     s6 = s3+" "+s5; 
     std::cout<<" "<<s6<<"\n"; 
     s5 = ""; 
     for(k = y;k<len-1;k++) 
     { 
      d[k] = str[k]; 
      s1 += d[k]; 
      s1 += " "; 
      for(int l = k+1;l<len;l++){ 
      b[l] = str[l]; 
      s2 += b[l]; 
     } 
     s4 = s3+" "+s1+s2; 
     s7 = s4; 
     std::cout<<" "<<s4<<"\n"; 
     s3 = "";s4 = ""; 
     } 
     s1 = "";s3 = ""; 
    } 
} 

int main(int argc, char* argv[]) 
{ 
    std::string str; 
    if(argc < 2) 
       std::cout<<"Usage: "<<argv[0]<<" <InputString> "<<"\n"; 
    else{ 
       str = argv[1]; 
       strsplit(str); 
    } 

return 0; 
}