문자에 여러 변형이있을 수있는 문자열의 가능한 모든 버전 찾기

Question

문자가 여러 변형을 가질 수있는 문자열의 가능한 모든 버전을 찾는 방법에 대한 팁을 찾고 있습니다.

간단한 예 : "Macao"는 시작 문자열입니다. 문자 'a'에는 변형 'ä'이 있고 문자 'o'에는 변형 'ö'이 있습니다.

목표는 위의 정보에서 다음 목록을 확보하는 것입니다

Macao 
Mäcao 
Macäo 
Mäcäo 
Macaö 
Mäcaö 
Macäö 
Mäcäö 

내 접근 방식은 지금까지 일을 단순화하는 변종 문자를 확인하고 추출 할 수있다. 아이디어는 전체 단어가 아닌 각 문자에 대해 작업하는 것입니다.

aao 
äao 
aäo 
ääo 
aaö 
äaö 
aäö 
ääö 

다음 코드는 우리가 작업하고있는 변형을 찾습니다.

다음 단계는 각각의 문자에 대해 가능한 모든 조합을 찾는 것입니다. 이를 위해 다음과 같은 기능을 썼습니다. results에 각 문자열의 첫 문자 중 새로운 문자열을 만듭니다.

std::string read_results(std::vector<std::string> &results) 
{ 
    std::string s; 
    for (auto &c : results) { 
     s.push_back(c.front()); 
    } 
    return s; 
} 

아이디어는 모든 가능한 조합을 얻을하는 방식으로 results에 저장된 문자열을 변경하는 것입니다, 나는 붙어 곳이다. 그게 도움이 될 것 같아 std::rotate 것 같습니다.

Answer 1

역 색인이 유용 할 수 있습니다.

벡터에 여러 변형이있는 모든 문자를 순서대로 정렬하고 각 문자에 대한 그룹화 색인이있는 벡터를 i 번째 문자가 그룹 I[i]에 속하도록 저장할 수 있습니다.

vector<vector<unsigned int> > groups; 
// groups[k] stores the indices in L of the letters that belongs to the k-th group. 
// do groups.reserve to make this operation more efficient 
for(size_t i = 0; i < L.size(); ++i) 
{ 
    unsigned int idx = I[i]; 
    if(idx <= groups.size()) groups.resize(idx+1); 
    groups[idx].push_back(i); 
} 

:

string L = "aoäöâô"; // disclaimer: i don't know if this is really in order 
unsigned int I[] = {0,1,0,1,0,1}; 
// this means that "aäâ" belong to group 0, and "oöô" belong to group 1 

당신은 이런 일에 이전 L 및 I의 역 색인을 구축 할 수 있습니다 : 지수는 I[i]이 같은 편지에서 변종보다 동일

L의 문자는 순서대로 정렬해야하므로 나중에 이진 검색을 수행 할 수 있습니다. 일반적인 검색의 경우 O(n) 대신 O(logn)이 필요합니다. 그런 다음 편지 그룹이 있으면 색인을 뒤집은 변종을 찾을 수 있습니다 :

char letter = 'a'; 
string::iterator it = std::lower_bound(L.begin(), L.end(), letter); 
if(it != L.end() && *it == letter) 
{ 
    unsigned int idx = I[ it - L.begin() ]; 
    // the letter has variants because it belongs to group idx 
    const vector<unsigned int>& group = groups[idx]; 
    for(vector<unsigned int>::const_iterator git = group.begin(); 
    git != group.end(); ++git) 
    { 
    // now, L[*git] is one of the variants of letter 
    ... 
    } 
}