-1

私はC++を学び、いくつかのオンラインチャレンジを行っています。しかし、私がいつも行き詰まっている「通常の」課題のほとんどはそうです。知識が不足しているのか、それとも単に考えすぎているのかわかりません。とにかく、誰かが私を助けてくれたら幸いです。

私はこの課題を実行しようとしています。たとえば、入力は数値「N」であり、後で「N」文字列を入力する必要があります。

次に、入力した文字列ごとに最小量のプレフィックスを見つけて、それらが繰り返されていないことを確認する必要があります。

たとえば、文字列「stackoverflow」には多くのプレフィックスがあります：s、st、sta、stac、stack、stacko、stackov、stackove、stackover、stackoverf、stackoverfl、stackoverflo、stackoverflow。

これらはすべてstackoverflowのプレフィックスです。したがって、別の文字列「standup」がある場合は、stackoverflowを入力する必要があります。stacはすでにstandupにあるため、standupの場合はstanになります。

前もって感謝します。

4

2 に答える 2

1

私が考えることができる最も単純なバージョン。

  • 単語のリストをアルファベット順に並べ替えます。最後から2番目の単語のコピーをリストに追加します。

  • リスト内の各単語の一意のプレフィックスは、リスト内の次の単語と比較して一意になる文字の数です。

例stackoverflow、、、。standup_seer

リストは次のようになります。

seer
stackoverflow
standup
stackoverflow

seer only requires `se` to be unique as compared to `stackoverflow`.
stackoverflow requires `stac` to be unique as compared to `standup`.
standup requires `stan` to be unique as compared to `stackoverflow`.

終わり。

于 2013-02-21T20:11:29.897 に答える
0

ツリーを作成する:(トライ？）

このツリーの各ノードに、文字（az）ごとに1つずつ、最大26の子があるとします。

ルートからリーフへのパスは文字列を示します。

        root
          \
           s
           |
           t
           |
           a
           /\
          c n
         /  |
        k   d
        |   |
        o   u
         ...

このツリーにすべてのアイテムを追加するだけです。

次に、深さ優先探索でツリーを処理します。サブツリーにリーフが1つしかないノードを取得するたびに（これらのカウントを追跡できます）、その文字列をこれまでに印刷して繰り返します。つまり、cとnは葉が1つしかないので、それぞれとを印刷stacしstanます。

上記のアプローチが大規模なC++プログラマーに特に適しているとは言えませんが、機能するコードを次に示します（CとC ++の悲惨な組み合わせと、以下のさまざまな残虐行為を許してください。これは非常に高速です。 -そして汚いアプローチ）

（リンク）

#include <string>
#include <iostream>
using namespace std;

class Node
{
  public:
    int count;
    Node *(children[26]); // array of pointers
    Node() { count = 0; for (int i = 0; i < 26; i++) children[i] = NULL; };
};

void add(char *s, Node &n)
{
    if (*s == 0) // null-terminator
      return;
    if (n.children[*s-'a'] == NULL)
      n.children[*s-'a'] = new Node();
    n.count++;
    add(s+1, *n.children[*s-'a']);
}

void print(char *start, char *end, Node &n)
{
    if (n.count == 1)
    {
        *end = 0; // null-terminator
        cout << start << endl;
        return;
    }
    for (int i = 0; i < 26; i++)
    {
        if (n.children[i] != NULL)
        {
            *end = (char)(i+'a');
            print(start, end+1, *n.children[i]);
        }
    }
}

int main()
{
    char *s = "stackoverflow";
    Node root;
    add(s, root);
    s = "standup";
    add(s, root);
    char output[1000]; // big buffer
    print(output, output, root);
}
于 2013-02-21T20:11:17.167 に答える