c++ - 查找字符串中不存在的最小子字符串

Question

我有一个仅包含数字 0-9 的字符串。字符串的长度可以介于 1 到 1,000,000 个字符之间。我需要在线性时间内找到字符串中不存在的最小数字。以下是一些示例:

1023456789       //Smallest number not in string is 11
1023479          //Smallest number not in string is 5
112131405678910  //Smallest number not in string is 15

对于 1,000,000 的大小，我认为字符串中不存在的最小数字最多为 6 位数字。

我的方法是生成从 0 到 999,999 的所有数字，并将它们全部插入一个 vector (按顺序)。然后制作一张 map ，标记哪些字符串已经被看到。然后我遍历字符串，对于每个位置，我得到从它开始的所有子字符串，大小为 1 到 6，并且我在映射中将所有这些子字符串标记为 true。最后，我只是一个一个地检查所有键，当我在 map 中找到第一个具有错误值的键时，我将其打印出来。

下面是一些代码片段:

string tmp="0";
string numbers[999999];

void increase(int pos)
{
    if(pos==-1)tmp.insert(0,"1");
    else if(tmp.at(pos)!='9')tmp.at(pos)++;
    else
    {
        tmp.at(pos)='0';
        increase(pos-1);
    }
}

//And later inside main
for(int j=0;j<999999;j++)
{
    numbers[j]=tmp;
    increase(tmp.size()-1);
}

---

for(int j=0;j<input.size();j++)
    {
        for(int k=0;k<6;k++)
        {
            string temp="";
            if(j+k<input.size())
            {
                temp+=input.at(j+k);
                appeared[temp]=true;
            }
        }
    }

---

int counter=0;
while(appeared[numbers[counter]])counter++;
cout<<numbers[counter]<<endl;

关于算法第一部分的注释。我生成一次 vector ，然后将其用于 100 个字符串。我需要在 4 秒内解析所有 100 个字符串。

目前这个算法对我来说太慢了。我可以优化一些代码，还是应该考虑采用不同的方法？

Answer 1

想法是建立一个满足的数字树:

class Node {
public:
    Node() : count( 0 ) {}
    // create a tree from substring [from, to[ interval
    void build( const std::string &str, size_t from, size_t to )
    {
        Node *node = this;
        while( from != to )
            node = node->insert( str[from++] );
    }

    std::string smallestNumber(  bool root = true, int limit = 0 ) const;

 private:
    Node *insert( char c ) 
    {
        int idx = c - '0';
        if( !children[idx] ) {
            ++count;
            children[idx].reset( new Node );
        }
        return children[idx].get();
    }

    int count;
    std::unique_ptr<Node> children[10];

};

std::string Node::smallestNumber( bool root, int limit ) const
{
    std::string rez;
    if( count < 10 ) { // for this node string is one symbol length
        for( int i = 0; i < 10; ++i )
            if( !children[i] ) return std::string( 1, '0' + i );
        throw std::sruntime_error( "should not happen!" );
    }
    if( limit ) { 
        if( --limit == 1 ) return rez; // we cannot make string length 1
    }
    char digit = '0';
    for( int i = 0; i < 10; ++i ) {
        if( root && i == 0 ) continue;
        std::string tmp = children[i]->smallestNumber( false, limit );
        if( !tmp.empty() ) {
            rez = tmp;
            digit = '0' + i;
            limit = rez.length();
            if( limit == 1 ) break;
        }
    }
    return digit + rez;
}

void calculate( const std::string &str )
{
    Node root;
    for( size_t i = 0; i < str.length(); ++i ) {
        root.build( str, i, i + std::min( 6UL, str.length() - i ) );
    }
    std::cout << "smallest number is:" << root.smallestNumber() << std::endl;
}

int main()
{
    calculate( "1023456789" );
    calculate( "1023479" );
    calculate( "112131405678910" );
    return 0;
}

编辑:经过一番思考，我意识到内循环是完全没有必要的。 1个循环就足够了。字符串长度限制为 6，我依赖于 OP 估计的最大可能数。

输出:

smallest number is:11
smallest number is:5
smallest number is:15