logo标签列表

寻找不在字符串中的最小子串

c++stringalgorithmsubstring
7
我有一个只包含数字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的所有数字，并将它们按顺序插入一个向量中。然后创建一个标记已经被看到过的字符串的映射表。接下来我遍历字符串，对于每个位置，获取以它为起点的所有子字符串（大小从1到6），并将所有这些子字符串在映射表中标记为true。最后，我逐个检查所有键，当我找到映射表中值为false的第一个键时，我打印它。

以下是一些代码片段：

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;

关于算法的第一部分，我会先生成一个向量，然后用它来处理100个字符串。我需要在不到4秒的时间内解析这100个字符串。

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

2
@A.Andevski，您是指与字符串长度相关的线性时间还是与子字符串数量相关的线性时间（与字符串长度的平方成正比）？我不确定前者是否可能。 - eerorika
2
这听起来像是一个竞赛中的问题 - 请提供链接以便我们知道它不是当前的。我可以想到一个算法，其时间复杂度与输入字符数和答案值成线性关系。 - j_random_hacker
2
我很想知道你是怎么得出170,000的。 - Jim Mischel
1
我明白了。170,000只是1,000,000/6（大概估算）而已。那可能太低了。例如考虑字符串“123456123”，它仅包含九个数字，但其中有四个六位数。可能可以想出一个接近该压缩比的排列方式。我怀疑你的最大值接近500,000。 - Jim Mischel
2
@JimMischel：可以看看de Bruijn序列；对于任何大小为k的字母表和任何整数n，您可以构造一个大小为k^n的循环，其中包含所有k^n个n字符序列。展开循环会产生一个长度为k^n + n-1的字符串，其第一个和最后一个n-1个字符相同。一个100万位数字序列只有999,995个6位子序列，因此至少有五个六位子序列不存在。特别地，一个de Bruijn序列（切割而不是展开）将恰好具有唯一子序列的数量。 - rici
显示剩余7条评论
4个回答
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
1
这是我解决问题的方法。思路是生成特定长度的唯一子字符串集，从最短的开始测试，然后再生成更长的子字符串。这样可以避免代码对结果上限做出假设，并且对于具有小结果的长输入字符串应该更快。但是，在大结果的最坏情况下，它不一定更好。
int find_shortest_subnumber(std::string str) {
    static int starts[10] = {
        0, 10, 100, 1000, 10000, 
        100000, 1000000, 10000000, 100000000, 1000000000
    };
    // can't find substrings longer than 9 (won't fit in int)
    int limit = std::min((int)str.size(), 9);
    for(int length = 1; length <= limit; length++) {
        std::set<std::string> uniques; // unique substrings of current length
        for(int i = 0; i <= (int)str.size() - length; i++) {
            auto start = str.begin() + i;
            uniques.emplace(start, start + length);
        }
        for(int i = starts[length - 1]; i < starts[length]; i++) {
            if(uniques.find(std::to_string(i)) == uniques.end())
                return i;
        }
    }
    return -1; // not found (empty string or too big result)
}

我还没有进行适当的复杂度分析。我用一个特定的测试字符串粗略地测试了这个函数，该字符串长度为1 028 880个字符，并且结果为190 000。在我的机器上执行需要大约2秒钟（其中包括生成测试字符串，这应该可以忽略不计）。
1
你可以在线性时间（和空间）内构建一个字符串的后缀树。一旦你有了后缀树，你只需要按字典顺序广度优先遍历它，扫描每个节点的子节点，并检查每个节点的所有10个数字。第一个缺失的数字是最小缺失数字的最后一个数字。
由于一个100万位数列只有999,995个六位子序列，因此至少有五个六位子序列不存在，所以广度优先搜索必须在第六层之前终止；因此，它也是线性时间的。
0

由于您只需要知道一个数字是否已经被查看过，所以最简单的方法可能是使用std::vector<bool>来存储该指示。当您遍历输入数字时，在数组中将数字标记为true。完成后，遍历数组，并打印仍为false的第一项的索引。

我需要一直将每个子字符串转换为整数，这样会不会花费更长的时间？ - A. Andevski
在这样一个小字符串中，我会说类型转换所需的时间不是一个因素，但检查它的唯一方法是实现并进行基准测试。但我会使用数组而不是向量。 - KjMag
@user3564091：向量通常由数组支持，而vector<bool>在将数据压缩到更少的空间中方面具有一些（臭名昭著的）优化。 - ssube
好的，但这次不是关于将其压缩到更小的空间，而是快速访问它，而这两个主题通常是相互矛盾的，如果我漏掉了什么，请纠正我。 - KjMag
除非数组非常小（特别是足够小以适应缓存），否则vector<bool>主要是为了交换额外的CPU时间以节省内存访问时间。您可以使用大量的CPU时间仅保存少量的内存访问，并且仍然可以获得优势。 - Jerry Coffin
显示剩余4条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接