問題タブ [string-algorithm]

接尾辞配列のLCP配列を計算する方法は? 最も効率的である必要はありません。O(n log n) または O(n) で十分です。可能であれば、比較的簡単にコーディングできるもの。

私の問題は、c の文字列内の一重引用符または二重引用符の数を数えられるようにすることです。例

ユーザーが文字列を入力し、gets() 関数を使用すると、文字列をさらに分析するためにこのカウンターが必要になります。

たとえば、文字列で「|」をカウントする必要がある場合は簡単でした。

私の機能は次のように単純でした：

しかし、引用符を分析する必要があるので、if(条件) に何を入れればよいかわかりません

S1 内の別の文字列 S2 に最も類似した部分文字列 (つまり、S2 とのハミング距離が最小である S1 内の部分文字列) を N log(N) で見つけるアルゴリズムを作成する必要があります。ここで、N = len(S1) + len(S2)、len(S2)<=len(S1)。

例:
S1 = AGTCAGTC
S2 = GTC
答え: GTC (距離 0)

S1 = AAGGTTCC
S2 = TCAA
答え: TTCC (距離 3)

時間の複雑さは O(N Log(N)) を超えることはできません。スペースの複雑さは問題ではありません。

私の場合、LCS (Longest Common Subsequence) は機能しません。例えば：

関数を書く

入力:
str: で終わる文字列\0。入力は、インプレース アルゴリズムが必要であることを示しています。

pattern：手紙。

replacement： 文字列。

mlen: メモリのサイズは、メモリstrの先頭から始まる文字列を保持し、mlenそれよりも大きくする必要がありますstrlen(str)

最終結果はまだ によって指されていstrます。

パターンの出現箇所はすべて置換する必要があることに注意してください。

例えば、

helelo\0...........

ここで「helelo」は、最後に置き換える文字列'\0'です。'\0'まだ L 有効なバイトがある後。「e」を「123」に置き換えます。

単純なアプローチは次のように機能strします。パターンが一致すると、残りのすべてを置換文字列を埋める場所にシフトし、パターンを置換で置き換えます。

元の文字列に長さnがあり、 のみが含まれている場合は、シフトがe必要です。(n-1) + (n-2) + ... + 1

文字列を 1 回のパスと一定のメモリ コストでスキャンするアルゴリズムはありますか?

与えられた単語リスト = { w1,w2,w3,w1,w2 }

長いテキストで上記の単語リストの順列をすべて検索します。

long text list = {これは長いテキスト w1 w2 w3 w4 およびw1 w2 w1 w2 w3です。これは、すべての単語 w1,w2,w2,w2,w2 が含まれているわけではないため、順列を持たないさらに別の長いテキストですが、これはスペースで区切られた順列w2 w2 w3 w1 w1 } です

この問題を解決する最も効率的なアルゴリズムは何ですか?

最初にリスト内の各一意の単語にタプル (一意の #、一意の素数 #) を割り当てて {w1 = [101, 5], w2 = [103, 7], w3 = [205, 11] }、合計を計算することを考えました割り当てられたタプルを使用したリスト全体の of : w1 [101 *5] + w2 [ 103 * 7] + w3 [ 205 * 11] + w1 [101 *5] + + w2 [ 103 * 7] = 4707

pudo コードは次のとおりです。

}

これにはより良いロジックやアルゴリズムがありますか?

アップデート ：

パターン マッチング Z アルゴリズム (Z ボックス) についてさらに読んでいましたが、すべての順列が事前にわかっていない限り、Z ボックスまたは Z 配列がどのように改善されるかわかりません。もっと良い方法があるかどうかわかりませんか？

知識を共有していただきありがとうございます。

ありがとう、

バベシュ

私はこのような文字列を持っていますDelete File/Folder。/に相当するものに基づいて文を分割する必要がありorます。

最後にDelete File、1 つの文字列Delete Folderとして、もう 1 つの文字列として、これから 2 つの文字列を生成する必要があります。

/私は、インデックスをチェックしてから、一連の条件で文字列を形成する非常に単純な方法を試しました。

のような文字列があると失敗することがありますFile/Folder Deleted。

編集：

分割すると/、ケース 1 の と が得Delete FileられFolderます。次に、最初の文字列に存在するスペースと、2 番目の文字列に存在するスペースを確認します。

スペースの数が少ないものは、最初の文字列の最後の要素に置き換えられます。これは複雑になってきています。

特定のリスト内の単語が記事に表示されるかどうかを示す次の簡単なコードがあります。

必要なのは、「キーワード」リストに少なくとも 3 つの単語が記事に含まれているかどうかです。含まれていない場合は、記事をスキップする必要があります。

これを行う簡単な方法はありますか？何も見つからないようです。