0

我有这段代码在其中提取 {} 之间的数据，这需要我大约 O(n) 是否有任何其他更有效的方法

#include <iostream>
#include <string>
#include <stdio.h>
int main()
{
   const char *blah = "[{post:banb {bbbbbbbb}: ananmsdb},{dsgdf{9090909090}fdgsdfg}";
   std::string op;
   unsigned int i = 0;    
   int im = 0;
   int found = 0;
   while(strlen(blah) != i){
       if(blah[i] == '{'){
         found = 1;  
         // copy what ever u got
         op+=blah[i];
         im++;  
       }
       else if(blah[i] == '}'){
           //copy wat ever u got
           op+=blah[i];
           im--;
       }
       if(found ==1){
           //copy wat ever u got.
           op+=blah[i];
       }

       if(found ==1 && im == 0)   {
           found = 0;
           cout << op <<endl;
           op.clear()  ;
           // u have found the full one post so send it for processing.
       }
i++;
}
}

输出:post:banb {bbbbbbbb}: anansdb dsgdf{9090909090}fdgsdfg

4

3 回答 3

3

不可以。您可以使用库函数来缩短此代码，但它永远不会比输入字符串的长度更有效O(n)，n因为您需要至少检查每个字符一次，因为每个字符都可能是您的标记需要提取。

于 2013-02-11T23:32:51.907 回答
1

我不认为你可以改进底层算法的 O(n) ，但你可能可以改进你的实现。

目前，您的实现可能是 O(n^2) 而不是 O(n)，因为strlen()可以在每次迭代时调用（除非您的编译器特别聪明）。您可能应该strlen()明确地缓存调用，例如更改：

while(strlen(blah) != i){
    ...

至：

const int len = strlen(blah);
while(len != i){
    ...
于 2013-02-11T23:32:28.420 回答
0

正如其他人所说，没有办法让它更快，因为你必须检查每个字符，以防你错过一个。

但是，如果你已经知道一些关于数据的信息，也就是有多少对“{”和“}”，那么我只能想到一种方法（除了排序，但这又回到了 O(n) + 等） .

这将是在 0 - x 之间选择索引，并在可以找到“{”或“}”的位置随机检查。需要明确的是，这只有在您知道数据集中已经有多少“{”和“}”时才有效。

编辑：当它点击第一个 cout<< 它应该输出“{{post:banb {{bbbbbbbb}}: ananmsdb}}”，因为它创建了额外的 {'s 和}的。

于 2013-02-11T23:56:03.783 回答