文字列マッチング素朴アルゴリズム
1086 ワード
この素朴なアルゴリズムの英語はBruteForceと命名され、暴力の意味であり、素朴なアルゴリズムとはアルゴリズム分析でよく言われる暴力の解法である.これは1種の方法で、1種のアルゴリズムの思想で、空間の時間の複雑さを考慮しないで、最も簡単な問題を見る視点で考えて、解決します.例えば八皇后問題では,全配列,多重ループ列挙の方式など,8重ループを用いて判断に従う.
文字列マッチング問題の素朴なアルゴリズムは文字列アルゴリズムの中で最も基本的で最も簡単なアルゴリズムと言える.彼は多くの人々の思考に基づいて、テキスト文字列がT[1,,,,n]、テンプレート文字列P[1,,,,m]であると仮定して、このような一致問題を考えている.m <= n;一般的には、テキストとテンプレートのアルファベット表は同じだと思います.0<=s<=n-m、T[s+1..s+m]=P[1..m]の整数sが存在する場合、テンプレートPはテキストTのオフセット(shift)sに現れると言ってもよいし、位置s+1に現れる(T[s+1]=P[1])と言ってもよい.文字列の問題はすべての合法的なオフセットを見つけることである.
アルゴリズムの説明は次のとおりです.
以下はC++実装コードです.
本の中で序数で表される下付き記号なので、私はやはり直接下付き記号ですべてを表して、循環などをコントロールします.
文字列マッチング問題の素朴なアルゴリズムは文字列アルゴリズムの中で最も基本的で最も簡単なアルゴリズムと言える.彼は多くの人々の思考に基づいて、テキスト文字列がT[1,,,,n]、テンプレート文字列P[1,,,,m]であると仮定して、このような一致問題を考えている.m <= n;一般的には、テキストとテンプレートのアルファベット表は同じだと思います.0<=s<=n-m、T[s+1..s+m]=P[1..m]の整数sが存在する場合、テンプレートPはテキストTのオフセット(shift)sに現れると言ってもよいし、位置s+1に現れる(T[s+1]=P[1])と言ってもよい.文字列の問題はすべての合法的なオフセットを見つけることである.
アルゴリズムの説明は次のとおりです.
以下はC++実装コードです.
本の中で序数で表される下付き記号なので、私はやはり直接下付き記号ですべてを表して、循環などをコントロールします.
// ,
#include
using std::string;
int AlmostBruteForce(string Text, string Pattern)
{
int lenT = Text.length();
int lenP = Pattern.length();
int s,i;
for (s = 0; s <= lenT-lenP; s++)
{
i = 0;
bool bEqual = true;
while (bEqual && (i < lenP))
{
if (Text[s+i] == Pattern[i])
{
i++;
}
else
{
bEqual = false;
}
}
if (bEqual)
{
return s;
}
}
return -1;
}