问字符串的连接并检查是否可以形成给定的字符串

EN

#include <vector>
#include <string>
#include <iostream>


using string = std::string;
using size_type= std::string::size_type;
using svector = std::vector<string>;

void eraseAllOccurences(const string& s, string& result){   

    string::size_type pos = string::npos;

    while ( (pos  = result.find(s) ) !=  string::npos){
        result.erase(pos, s.length());
    }    
}



int main(int, char**){

    const string targetString = "bcaaac";   
    const svector candidates = { "a", "b", "c" };

    string result = targetString;

    for(auto s : candidates)
        eraseAllOccurences(s, result);  

    std::cout << (result.empty() ? "success" : "failure") << '\n';

    return 0;
}

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <string_view>

using std::cout;
using std::string;
using size_type = std::string::size_type;
using svector = std::vector<string>;        //string vector
using ivector = std::vector<std::size_t>;   //index vector
using sview = std::string_view;
using sviews = std::vector<sview>;

inline bool isSubStringOf(sview str, sview substr){
    return str.find(substr) != string::npos;
}

inline bool startsWith(sview str, sview prefix) {
    return str.size() >= prefix.size() && str.compare(0,  prefix.size(), prefix) == 0;
}

// just to hold the alphabet not really, could just use a vector. Was more for debug.
class Alphabet{
public:
    Alphabet() = default;
    Alphabet(const Alphabet&) = default;
    Alphabet(Alphabet&&) = default;
    Alphabet& operator=(const Alphabet&) = default;
    Alphabet& operator=(Alphabet&&) = default;
    Alphabet(const svector& sv) : m_letters(sv){}
    ~Alphabet() = default;

    ivector prefixLengths(sview str) const;
    const svector& letters() const { return m_letters; }
    void prepare(const string&);

private:
    svector m_letters;
};


// prepare alphabet by removing junk
void Alphabet::prepare(const string& str)
{

    //remove duplicate strings
    std::sort(m_letters.begin(), m_letters.end());
    m_letters.erase( std::unique( m_letters.begin(), m_letters.end() ), m_letters.end() );

    for(auto it = m_letters.begin() ; it != m_letters.end(); ) {
        if (it->empty())                    //remove empty strings
            it = m_letters.erase(it);
        else if(!isSubStringOf(str, *it))   //remove letters that don't appear in str
            it = m_letters.erase(it);
        else
            ++it;
    }
}


// return vector of the unique lengths of all letters that start the word str
ivector Alphabet::prefixLengths(sview str) const
{
    ivector result;
    for(auto prefix : m_letters)
        if(startsWith(str, prefix))
            result.push_back(prefix.size());

    return result;
}


// create a vector of string views by removing prefixes from given views
sviews nextViews(const sviews& views, const Alphabet& strings)
{
    sviews result;
    for(auto v : views){
        auto lengths = strings.prefixLengths(v);
        for(auto e : lengths){
            sview sv(v);
            sv.remove_prefix(e);
            result.push_back(sv);
        }
    }
    // ["a", "bc"] and ["ab", "c"] will both yield a prefix length of 3
    // so we will get the same view of the word so remove duplicates views
    std::sort(result.begin(), result.end());
    result.erase( std::unique( result.begin(), result.end() ), result.end() );

    return result;
}



int main(int, char**)
{
    const string word = "abcdabcdabcdbccbcabchk";
    const svector letters = { "ab", "abc", "c", "bc", "cd", "hk" };


    // tidy up the alphabet to only include letters that appear in the word
    // and remove empty letters and duplicates
    Alphabet alphabet(letters);
    alphabet.prepare(word);

    // we start with a view of the original word
    sviews views = { word };

    // keep stripping off prefixes from the views until we get an empty view
    // or we have no more to try
    while(!views.empty()){
        bool success = std::find_if(
            views.begin(),
            views.end(),
            [](auto e){ return e.empty(); })  != views.end();

        if(success){
            cout << "success\n";
            return 0;
        }
        views = nextViews(views, alphabet);
    }

    cout << "fail\n"; // we ran out of views to find prefixes for
    return 0;
}

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <string_view>
#include <set>

using std::cout;
using std::string;
using svector = std::vector<string>;        // string vector
using ivector = std::vector<std::size_t>;   // index vector
using sview = std::string_view;             // string_view
using iset = std::set<std::size_t>;         // index set



inline bool isSubStringOf(sview str, sview substr){
    return str.find(substr) != string::npos;
}


inline bool startsWith(sview str, sview prefix) {
    return str.size() >= prefix.size() && str.compare(0, prefix.size(), prefix) == 0;
}


// prepare alphabet by removing junk
svector prepare(const svector& letters, const string& word)
{
    svector result = letters;

    //remove duplicate strings
    std::sort(result.begin(), result.end());
    result.erase( std::unique( result.begin(), result.end() ),   result.end() );

    for(auto it = result.begin() ; it != result.end(); ) {
        if (it->empty())                    //remove empty strings
            it = result.erase(it);
        else if(!isSubStringOf(word, *it))  //remove strings that don't appear in word
            it = result.erase(it);
        else
            ++it;
    }
    return result;
}


// vector of lengths of letters that prefix str
ivector prefixLengths(sview str, const svector& letters)
{
    ivector result;
    for(auto& prefix : letters)
        if(startsWith(str, prefix))
            result.push_back(prefix.size());

    return result;
}


// return view of string advanced by i chars
sview advanceViewOf(std::size_t i, const string& str)
{
    sview view(str);
    view.remove_prefix(i);
    return view;
}


// return set of indices into word for all prefixes
iset nextIndexSet(const iset& indices, const string& word, const svector& letters)
{
    iset result;
    for(std::size_t i : indices){
        for(std::size_t length : prefixLengths(advanceViewOf(i, word), letters))
            result.insert(i + length);
    }
    return result;
}


const string word = "abcdabcdabcdbccbcabchk";
const std::size_t wordLength = word.size();
const svector letters = { "a", "ab", "abc", "c", "bc", "cd", "hk" };


int main(int, char**)
{
    svector alphabet = prepare(letters, word);
    iset indices = {0};

    do{
        bool success = indices.find(wordLength) != indices.end();
        if(success){
            cout << "success\n";
            return 0;
        }
        indices = nextIndexSet(indices, word, letters);
    }while(!indices.empty());

    cout << "fail\n";

    return 0;
}