-2

n文字の組み合わせで構成される長さの文字列が与えられますA B D。

例-1:AAAABAAAADADDDDADDDBBBBBBDDDDA

Thresholdof x、指定された部分文字列には、最大長の他の連続した部分文字列を含めることができますx

Ex-2: AEx-1のサブシーケンスのAAAABAAAADA場合、しきい値の (1,11) 境界を持つ正当な部分文字列ですx = 2。

同様に、主な文字列を無視して、 と の部分文字列を個別Aに抽出したいと思います。メイン文字列には、各タイプのサブ文字列が多数存在する場合があります。DB

モデル出力:

Type Boundaries
A    1,11
D    12,20
D    26,29

Aしきい値より大きい距離が文字列を壊した場合、s間の距離を見つけることによって非効率的な非アルゴリズムの方法を実装しました。と に対してこれを個別に実行する必要がAありDました。これにより、境界領域が重なります。

これを解決するためのより良いアプローチはありますか?

編集-1

有効な部分文字列は任意の長さにできますが、しきい値より大きい他の部分文字列によって汚染されてはなりませんx。つまり、その部分文字列の検索中に、他の文字が含まれていたり、連続してしきい値よりも大きくなったりしAてはなりません。BD

x = 2の検索中AにAABBAAAA, AABDAAAAが有効であるが、 ではない場合AADBDAAA, AABBBAAA。A同様に、D（およびB汚染物質になります）を検索している間。

「Pham Trung」の回答を使用したEDIT-2実装

コード：

start = 0
lastA = -1
lastD = -1
x = 2

arr = ["A", "A", "A", "A", "B", "A", "A", "A", "A", "D", "A", "D", "D", "D", "D", "A", "D", "D", "D", "B", "B", "B", "B", "B", "B", "D", "D", "D", "D", "A"]

for i in range(0, len(arr)):
    if(arr[i] == 'A'):
        if(lastA != -1 and i - lastA > x):
            print("A", start + 1, lastA + 1)
            start = i
        lastA = i
    elif(arr[i] == 'D'):
        if(lastD != -1 and i - lastD > x):
            print("D", start + 1, lastD + 1)
            start = i
        lastD = i

出力：

A 1 11
D 16 19
A 26 16

コードは部分文字列の後に1st部分文字列を抽出できません。

4

1 に答える 1

1

したがって、ここにあなたの問題に対するいくつかの提案があります：

文字列には 3 種類の文字しかないため、これらの文字の最後の位置を簡単に追跡できます。

文字列の先頭から開始し、現在の文字とその最後の位置の間の距離を追跡し、それがしきい値よりも大きい場合は、それを分割してそこから新しい部分文字列を開始します。

擬似コード:

int start = 0;
int lastA = -1;
int lastD = -1;
for(int i = 0; i < input.length(); i++)
    if(input.charAt(i) == 'A'){
       if(lastA != -1 && i - lastA > x){
           create a substring from start to i - 1; 
           start = i; //Update the new start for the next substring
           lastD = -1;//Reset count for D
       }
       lastA = i;
    }else if(input.charAt(i) == 'D'){
       //Do similar to what we do for character A
    } 
}
create a substring from start to end of the string; //We need to add the last substring.

Python コードを更新します。

start = 0
lastA = -1
lastD = -1
x = 2

arr = ["A", "A", "A", "A", "B", "A", "A", "A", "A", "D", "A", "D", "D",    "D","D", "A", "D", "D", "D", "B", "B", "B", "B", "B", "B", "D", "D", "D", "D", "A"]

for i in range(0, len(arr)):
    if(arr[i] == 'A'):
        if(lastA != -1 and i - lastA > x):
            print("A", start + 1, lastA + 1)
            start = lastA + 1
            while(start < len(arr) and arr[start] == 'B'):
                start = start + 1
            lastD = -1 
        lastA = i
    elif(arr[i] == 'D'):
        if(lastD != -1 and i - lastD > x):
            print("D", start + 1, lastD + 1)
            start = lastD + 1
            while(start < len(arr) and arr[start] == 'B'):
                start = start + 1
            lastA = -1
        lastD = i
while(start < len(arr) and arr[start] == 'B'):
    start = start + 1 
if(start < len(arr)):   
   print("A or D", start + 1, len(arr))
于 2015-12-23T09:11:58.143 に答える