Блог

Описание вопроса относительно простое, приведен пример

 input: 10100011
output: 110
 

Я пробовал использовать BFS, но я не думаю, что это достаточно эффективное решение (может быть, какое-то растровое изображение скользящее окно?)

 string IntToString(int a)
{
    ostringstream temp;
    temp << a;
    return temp.str();
}

bool is_subsequence(stringamp; s, stringamp; sub) {
    if(sub.length() > s.length()) return false;
    int pos = 0;
    for(char c : sub)
    {
        pos = s.find(c, pos);
        if(pos == string::npos) return false;
          pos;
    }
    return true;
}

string shortestNotSubsequence(stringamp; s) {
    Queue q(16777216);
    q.push(0);
    q.push(1);
    while(!q.empty())
    {
        string str;
        int num = q.front; q.pop();
        str = IntToString(num);
        if(!is_subsequence(s, str)) return str;
        string z = str   '0';
        string o = str   '1';
        q.push(stoi(str '0'));
        q.push(stoi(str '1'));
    }
    return "";
}

int main() {
    string N;
    cin >> N;
    cout << shortestNotSubsequence(N) << endl;
    return 0;
}
 

Вы можете сделать это довольно легко за O (N) времени.

Пусть W = ceiling(log ₂(N 1)), где N — длина входной строки S.

Существует 2 возможных строки длиной ^W. В S должно быть меньше N подстрок, а это меньше 2 ^W, поэтому по крайней мере одна строка длиной W не должна присутствовать в S.

W также меньше, чем количество битов в a size_t , и требуется всего O (N) места для хранения маски всех возможных строк длины W. Инициализируйте такую маску до 0s, а затем выполните итерацию по S, используя младшие W бит в a size_t в качестве скользящего окна подстрок, с которыми вы сталкиваетесь. Установите бит маски для каждой встречающейся подстроки равным 1.

Когда вы закончите, просканируйте маску, чтобы найти первый 0, и это будет строка длиной W, которая отсутствует.

Однако могут быть и более короткие отсутствующие строки, поэтому объедините биты маски попарно, чтобы создать маску для строк длиной W-1, а затем также установите бит маски для последних W-1 битов в S, поскольку они могут не быть включены ни в одну строку длиной W. Затем просканируйте маску на 0 секунд, чтобы увидеть, сможете ли вы найти более короткую отсутствующую строку.

Пока вы продолжаете находить более короткие строки, продолжайте объединять маску для строк меньшего размера, пока не достигнете длины 1. Поскольку каждая такая операция делит размер маски на 2, это не влияет на общее время O (N) для всего алгоритма.

Вот реализация на C

 #include <string>
#include <vector>
#include <algorithm>

std::string shortestMissingBinaryString(const std::string instr) {
    const size_t len = instr.size();
    if (len < 2) {
        if (!len || instr[0] != '0') {
            return std::string("0");
        }
        return std::string("1");
    }
    // Find a string size guaranteed to be missing
    size_t W_mask = 0x3;
    unsigned W = 2;
    while(W_mask < len) {
        W_mask |= W_mask<<1;
        W =1;
    }

    // Make a mask of all the W-length substrings that are present
    std::vector<bool> mask(W_mask 1, false);
    size_t lastSubstr=0;
    for (size_t i=0; i<len;   i) {
        lastSubstr = (lastSubstr<<1) amp; W_mask;
        if (instr[i] != '0') {
            lastSubstr |= 1;
        }
        if (i 1 >= W) {
            mask[lastSubstr] = true;
        }
    }

    //Find missing substring of length W
    size_t found = std::find(mask.begin(), mask.end(), false) - mask.begin();

    // try to find a shorter missing substring
    while(W > 1) {
        unsigned testW = W - 1;
        W_mask >>= 1;
        // calculate masks for length testW 
        for (size_t i=0; i<=W_mask; i  ) {
            mask[i] = mask[i*2] || mask[i*2 1];
        }
        mask.resize(W_mask 1);
        // don't forget the missing substring at the end
        mask[lastSubstr amp; W_mask] = true;

        size_t newFound = std::find(mask.begin(), mask.end(), false) - mask.begin();
        if (newFound > W_mask) {
            // no shorter string
            break;
        }
        W = testW;
        found = newFound;
    }

    // build the output string
    std::string ret;
    for (size_t bit = ((size_t)1) << (W-1); bit; bit>>=1) {
        ret.push_back((found amp; bit) ? '1': '0');
    }
    return ret;
}