algorithm - 空白に関係なく文字列を検索する

Question

、、、、、を含むフレーズ"a"のArrayList があります。入力はまたはの可能性があります。どちらの場合も、ArrayListと一致する必要があります。そのためのアルゴリズムが必要です。"b""ab""ab c""ab cd""ab c""ab    c""ab c"

Answer 1

あなたが本当に求めているのは、複数のスペースを単一のスペースに置き換える方法です。これはあなたが必要とするものかもしれません:この質問を参照してください。

Answer 2

使用している言語はわかりませんが、最も単純な疑似コードは次のとおりです。

f(string inString, ArrayList<string> list):
    string s = inString.removeAllWhitespace();
    foreach (string s2 in list):
        string lString = s2.removeAllWhitespace();
        if (s.equals(lString))
            return true

    return false

より速くしたい場合は、次のようにしてみてください。

f(string inString, ArrayList<string> list):
    foreach (string s in list):
        i1 = 0
        i2 = 0
        while (i1 < inString.length && i2 < s.length):
            if (iswhitespace(inString[i1])):
                i1++
            else if (iswhitespace(s[i2])):
                i2++
            else if (inString[i1] == s[i2]):
                i1++
                i2++
            else:
                continue foreach

        # account for trailing whitespace in both strings
        while (i1 < inString.length):
            if (!iswhitespace(inString[i1])):
                break
            i1++
        while (i2 < s.length):
            if (!iswhitespace(s[i2])):
                break
            i2++

        # strings are equal if we reached the end of both without
        # finding different characters (ignoring whitespace)
        if (i1 == inString.length && i2 == s2.length):
            return true
    return false

これは、一意のインデックスを持つ各文字列を反復処理し、空白が見つかるか一致するとインクリメントします。文字が一致しない場合、文字列は拒否され、外側のループが続行されます。

この疑似コードはテストされていませんが、その方法については理解できるはずです。空白を削除する方法をお勧めします。これは非常に単純なコードであり、遅すぎず、何をしようとしているのかについて非常に明白な手がかりを読者に提供します。

ほとんどの言語では、文字列は不変であるため、この置換を行っても ArrayList 内の文字列には影響しません。

Answer 3

bool hacked_compare(const string& s, const string& t){
    string::const_iterator si = s.begin(), ti = t.begin();
    while (si != s.end() && ti != t.end() && (isspace(*si) || isspace(*ti))){
        // ignore all spaces leading to next char.
        while (si != s.end() && isspace(*si))
            si++;
        while (ti != t.end() && isspace(*ti))
            ti++;
        // check for equality of two chars.
        if (*si != *ti)
            return false;
        // keep going through both strings.
        si++;
        ti++;
    }
    //if we got this far then the strings were "equivalent" or empty.
    return true;
}