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}: ananmsdb dsgdf{9090909090}fdgsdfg

4

3 に答える 3

3

ライブラリ関数を使用してこのコードを短くすることはできますが、入力文字列の長さよりも効率的であることはありませんO(n)。n抽出する必要があります。

于 2013-02-11T23:32:51.907 に答える
1

基礎となるアルゴリズムの O(n) を改善できるとは思いませんが、おそらく実装を改善できます。

現在、実装は O(n) ではなく O(n^2) であるstrlen()可能性があります (コンパイラが特にスマートでない限り)。おそらく、呼び出しをstrlen()明示的にキャッシュする必要があります。たとえば、次のように変更します。

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

に：

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

他の誰もが言っているように、これをより速くする方法はありません。

しかし、これは、おそらくデータに関する情報、つまり「{」と「}」のペアの数をすでに知っている場合、1つの方法しか考えられないと言われています（ソート以外に、それはO（n）+などに戻ります） .

これは、0 から x の間のインデックスを選択し、「{」または「}」が見つかるかどうかスポットをランダムにチェックすることです。明確にするために、これは、データのセットに既にいくつの「{」と「}」があるかを知っている場合にのみ機能します。

編集：追加のコピーを（メモ帳を使用して）最初のcout<<にヒットしたときに、「{{post:banb {{bbbbbbbb}}: ananmsdb}}」を出力する必要があります。追加の{と}を作成するためですの。

于 2013-02-11T23:56:03.783 に答える