6

文字列 S と、他の文字列のリスト L が与えられたとします。

S が L のすべての可能な連結の 1 つであるかどうかをどのように知ることができますか?

例えば：

S = "abcdabce"

L = ["abcd", "a", "bc", "e"]

S が "abcd" + "a" + "bc" + "e" の場合、S は L の連結ですが、"ababcecd" はそうではありません。

この質問を解決するために、DFS/バックトラッキングを使用しようとしました。擬似コードは次のとおりです。

boolean isConcatenation(S, L) {
    if (L.length == 1 && S == L[0]) return true;
    for (String s: L) {
        if (S.startwith(s)) {
            markAsVisited(s);
            if (isConcatnation(S.exclude(s), L.exclude(s))) 
                return true;
            markAsUnvisited(s);
        }
    }
    return false;
}

ただし、DFS/バックトラッキングは効率的なソリューションではありません。この質問を解決するための最速のアルゴリズムは何か、またはそれをより高速に解決するための他のアルゴリズムがあるかどうかに興味があります。O(n) 時間で解決できる KMP のようなアルゴリズムがあることを願っています。

4

7 に答える 7

3

パイソンでは：

>>> yes = 'abcdabce'
>>> no = 'ababcecd'
>>> L = ['abcd','a','bc','e']
>>> yes in [''.join(p) for p in itertools.permutations(L)]
True
>>> no in [''.join(p) for p in itertools.permutations(L)]
False

編集：指摘したように、これはnです！複雑なので、大きな L には適していません。しかし、開発時間は 10 秒未満です。

代わりに、基本的な順列子から始めて、独自の順列ジェネレーターを構築できます。

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]

次に、要素の連結がどうなるかを追跡し、それがターゲット文字列になる場合にのみ反復することで、気にしない分岐を破棄します。

    def all_perms(elements, conc=''):
    ...
            for perm in all_perms(elements[1:], conc + elements[0]):
    ...
                if target.startswith(''.join(conc)):
    ...
于 2013-07-18T19:20:17.397 に答える
2

動的プログラミングのアプローチは、左から右に作業し、配列 A[x] を構築することです。ここで、文字列の最初の x 文字が L の可能な連結の 1 つを形成する場合、A[x] は true です。 n] リスト内の可能な各文字列をチェックすることにより、前に A[n] を指定します - S の文字から n 番目の文字までが長さ k の候補文字列と一致し、A[nk] が true の場合、A[n を設定できます。 ] 真実。

https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithmを使用して、動的プログラムへの入力として必要な一致を見つけることができることに注意してください-一致コストは入力のサイズに比例します文字列、すべての候補文字列の合計サイズ、および入力文字列と候補文字列の間の一致数。

于 2013-07-18T19:21:06.430 に答える
0

Haskell の 2 つの命題:

これにはいくつかの反例があるかもしれません...ただの楽しみのために...カスタムソートでLをソートします：

import Data.List (sortBy,isInfixOf)

h s l = (concat . sortBy wierd $ l) == s where
  wierd a b | isInfixOf (a ++ b) s = LT
            | isInfixOf (b ++ a) s = GT
            | otherwise            = EQ


もっとつまらない... L から S を構築しようとする:

import Data.List (delete,isPrefixOf)

f s l = g s l [] where
  g str subs result
    | concat result == s = [result]
    | otherwise   = 
        if null str || null subs' 
           then []
           else do sub <- subs'
                   g (drop (length sub) str) (delete sub subs) (result ++ [sub])
   where subs' = filter (flip isPrefixOf str) subs

出力：

*Main> f "abcdabce" ["abcd", "a", "bc", "e", "abc"]
[["abcd","a","bc","e"],["abcd","abc","e"]]

*Main> h "abcdabce" ["abcd", "a", "bc", "e", "abc"]
False

*Main> h "abcdabce" ["abcd", "a", "bc", "e"]
True
于 2013-07-18T21:03:08.227 に答える
0

アルゴリズムの複雑さは N^2 (N はリストの長さ) です。実際の C++ で見てみましょう

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

typedef pair<string::const_iterator, string::const_iterator> stringp;
typedef vector<string> strings;

bool isConcatenation(stringp S, const strings L) {
    for (strings::const_iterator p = L.begin(); p != L.end(); ++p) {
        auto M = mismatch(p->begin(), p->end(), S.first);
        if (M.first == p->end()) {
            if (L.size() == 1)
                return true;
            strings T;
            T.insert(T.end(), L.begin(), p);
            strings::const_iterator v = p;
            T.insert(T.end(), ++v, L.end());
            if (isConcatenation(make_pair(M.second, S.second), T))
                return true;
        }
    }
    return false;
}

ベクトル全体をループする代わりに、それを並べ替えてから、すべての文字列が異なる文字で始まる最適なケースでは、検索を O(LOG(N)) ステップに減らすことができます。最悪の場合は O(N^2) のままです。

于 2013-07-18T21:38:45.803 に答える
0

私はこの解決策を提案します：

  1. L のすべての文字列の各文字の出現回数を格納するサイズ 256 の配列を取得します。次に、それを S の各文字の回数と一致させます。両方が等しくない場合、それらは特定の文字を形成できないと自信を持って言えます。 .
  2. カウントが同じ場合、KMP アルゴリズムを使用して、S 内の L 内の各文字列を同時に検索しようとする次の手順を実行します。いつでも一致する場合は、その文字列を L から削除し、L 内の他の文字列の検索を続けます。表現できないことを印刷するだけの一致は見つかりません。最後に L が空の場合、S は実際に L の連結であると結論付けます。

L が一意の文字列のセットであると仮定します。

于 2013-07-18T20:28:46.780 に答える
0

Trieデータ構造を使用できます。まず、L の文字列からトライを構築します。

次に、入力文字列 S について、トライで S を検索します。

検索中、L 内の単語の 1 つの末尾であるすべての訪問済みノードに対して、S の残りの (まだ一致していない) サフィックスを使用して (ルートから) トライで新しい検索を呼び出します。したがって、再帰を使用しています。そのプロセスで S のすべての文字を消費すると、S が L からのいくつかの文字列の連結であることがわかります。

于 2013-07-18T20:24:47.133 に答える