1

いくつかの短い文字列があるとしましょう:

string[] shortStrings = new string[] {"xxx","yyy","zzz"}; (この定義は配列と文字列の長さを変更する可能性があるため、固定されたものではありません)

特定の文字列が shortStrings のみと組み合わされているかどうかを確認したいのですが、どうすればよいですか?

関数が次のようであるとしましょうbool TestStringFromShortStrings(string s)

それから

TestStringFromShortStrings("xxxyyyzzz") = true;
TestStringFromShortStrings("xxxyyyxxx") = true;
TestStringFromShortStrings("xxxyyy") = true;
TestStringFromShortStrings("xxxxxx") = true;
TestStringFromShortStrings("xxxxx") = false;
TestStringFromShortStrings("xxxXyyyzzz") = false;
TestStringFromShortStrings("xxx2yyyxxx") = false;

緊張せず、比較的速い記憶方法を提案してください。

[EIDT] この関数は何のためですか?

私は個人的にこの関数を使用して、文字列がPINYINの組み合わせであるかどうかをテストします。以下の中国語は読めなくても同じです。

检测一文字列是否は汉语拼音(例:检测是拼音域名) すべての汉语拼音字列有:</p>

(文字列が羽生ピンインかどうかを検出するには (例: ピンイン文字列の音声ドメインを検出します):)

Regex PinYin = new Regex(@"^(a|ai|an|ang|ao|ba|bai|ban|bang|bao|bei|ben|beng|bi|bian|biao|bie|bin|bing|bo|bu|ca|cai|can|cang|cao|ce|cen|ceng|cha|chai|chan|chang|chao|che|chen|cheng|chi|chong|chou|chu|chua|chuai|chuan|chuang|chui|chun|chuo|ci|cong|cou|cu|cuan|cui|cun|cuo|da|dai|dan|dang|dao|de|den|dei|deng|di|dia|dian|diao|die|ding|diu|dong|dou|du|duan|dui|dun|duo|e|ei|en|eng|er|fa|fan|fang|fei|fen|feng|fo|fou|fu|ga|gai|gan|gang|gao|ge|gei|gen|geng|gong|gou|gu|gua|guai|guan|guang|gui|gun|guo|ha|hai|han|hang|hao|he|hei|hen|heng|hong|hou|hu|hua|huai|huan|huang|hui|hun|huo|ji|jia|jian|jiang|jiao|jie|jin|jing|jiong|jiu|ju|juan|jue|jun|ka|kai|kan|kang|kao|ke|ken|keng|kong|kou|ku|kua|kuai|kuan|kuang|kui|kun|kuo|la|lai|lan|lang|lao|le|lei|leng|li|lia|lian|liang|liao|lie|lin|ling|liu|long|lou|lu|lv|luan|lue|lve|lun|luo|ma|mai|man|mang|mao|me|mei|men|meng|mi|mian|miao|mie|min|ming|miu|mo|mou|mu|na|nai|nan|nang|nao|ne|nei|nen|neng|ni|nian|niang|niao|nie|nin|ning|niu|nong|nou|nu|nv|nuan|nuo|nun|ou|pa|pai|pan|pang|pao|pei|pen|peng|pi|pian|piao|pie|pin|ping|po|pou|pu|qi|qia|qian|qiang|qiao|qie|qin|qing|qiong|qiu|qu|quan|que|qun|ran|rang|rao|re|ren|reng|ri|rong|rou|ru|ruan|rui|run|ruo|sa|sai|san|sang|sao|se|sen|seng|sha|shai|shan|shang|shao|she|shei|shen|sheng|shi|shou|shu|shua|shuai|shuan|shuang|shui|shun|shuo|si|song|sou|su|suan|sui|sun|suo|ta|tai|tan|tang|tao|te|teng|ti|tian|tiao|tie|ting|tong|tou|tu|tuan|tui|tun|tuo|wa|wai|wan|wang|wei|wen|weng|wo|wu|xi|xia|xian|xiang|xiao|xie|xin|xing|xiong|xiu|xu|xuan|xue|xun|ya|yan|yang|yao|ye|yi|yin|ying|yo|yong|you|yu|yuan|yue|yun|za|zai|zan|zang|zao|ze|zei|zen|zeng|zha|zhai|zhan|zhang|zhao|zhe|zhei|zhen|zheng|zhi|zhong|zhou|zhu|zhua|zhuai|zhuan|zhuang|zhui|zhun|zhuo|zi|zong|zou|zu|zuan|zui|zun|zuo)+$");

以下の正则表現式の方法を使用して、了解しました。

(正規表現で試してみました。最も単純で非常に良い結果が得られますが、少し遅いです。長い文字列の再帰的な方法は面倒で、スタックをオーバーフローさせるのは簡単すぎます。)

4

3 に答える 3

4

編集:LBとミリムースのおかげでこれを大幅に簡素化しました。

救助への正規表現!を使用するSystem.Text.RegularExpressions.Regexと、次のようになります。

public static bool TestStringFromShortStrings(string checkText, string[] pieces) {
    // Build the expression.  Ultimate result will be
    // of the form "^(xxx|yyy|zzz)+$".
    var expr = "^(" + 
               String.Join("|", pieces.Select(Regex.Escape)) + 
               ")+$";

    // Check whether the supplied string matches the expression.
    return Regex.IsMatch(checkText, expr);
}

これにより、長さが異なる複数のパターンが繰り返されるケースを適切に処理できるはずです。たとえば、可能なピースのリストに文字列"xxx""xxxx".

于 2012-08-02T21:42:43.023 に答える
2

ターゲット文字列を文字列ビルダーにコピーします。shortstring 配列内の各文字列について、すべての出現箇所をターゲットから削除します。長さが 0 の文字列になる場合は true、それ以外の場合は false。

編集:このアプローチは正しくありません。コメントを参照してください。最初はかなり正しいように見えるかもしれないので、この答えをここに残しておきます。

于 2012-08-02T21:38:48.163 に答える
2

入力文字列の開始を各短い文字列と比較できます。一致するとすぐに、残りの文字列を取得して繰り返します。弦がなくなったら完成です。例えば:

string[] shortStrings = new string[] { "xxx", "yyy", "zzz" };

bool Test(string input)
{
    if (input.Length == 0)
        return true;

    foreach (string shortStr in shortStrings)
    {
        if (input.StartsWith(shortStr))
        {
            if (Test(input.Substring(shortStr.Length)))
                return true;
        }
    }
    return false;
}

再帰を削除するか、短い文字列を並べ替えて線形検索の代わりにバイナリを実行することで、これを最適化できます。


Stackこれは、代わりにオブジェクトを使用する非再帰バージョンです。を取得する可能性はありませんStackOverflowException:

string[] shortStrings = new string[] { "xxx", "yyy", "zzz" };

bool Test(string input)
{
    Stack<string> stack = new Stack<string>();
    stack.Push(input);

    while (stack.Count > 0)
    {
        string str = stack.Pop();
        if (str.Length == 0)
            return true;
        foreach (string shortStr in shortStrings)
        {
            if (str.StartsWith(shortStr))
                stack.Push(str.Substring(shortStr.Length));
        }
    }
    return false;
}
于 2012-08-02T21:42:15.683 に答える