今日は簡単な文字列比較プログラムを作りました。機能は、A 文字列から B を含む文字を最も多く削除する操作を実現することです。例えば、A="aaaaabbbbbbabababa"、B="aaccbaab" の場合、"aab" を削除する必要があります。aa ではなく、検索エンジンを知っている友達はきっと知っていると思います。このアルゴリズムは、ページ内の無効なキーワードを削除して、収集にかかる計算コストを減らすための方法です。さて、具体的なアルゴリズムは明日に持ち越しましょう。しかし、今日話すのは 2 つの一般的に使用される文字列マッチングアルゴリズム、KMP アルゴリズムとインデックス法です。
KMP アルゴリズムは、Knuth、Morris、Pratt の 3 人の先人が提案した文字列の高速マッチングアルゴリズムで、KMP アルゴリズムと略されます。非常に有名なアルゴリズムであり、BM アルゴリズムや AB-BM アルゴリズムなど、さらなる発展もありますが、今度話します。最近はブログを書く時間がないので、原理は非常にシンプルで、追加の数値を使用してマッチングの回数を記録し、その結果に基づいて計算を行う方法です。分からない？参照してください
http://www.chinaitpower.com/A/2003-01-04/45995.html
インデックス法は、最も単純な文字列マッチングアルゴリズムです。原理は、一つずつ試して、最初の一致を見つけた後、次の一致を見つけるかどうかを確認し、文字列の末尾まで続けることです。非常にクラシックなアルゴリズムです。
以下に、コードの簡単な比較を行います：
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
/*getnext*/
void getNext(char p[],int next[]){
int i, j, slen;
slen = strlen(p);
i = 0;
j = -1;
next[0] = -1;
while(i < slen){
if((j == -1) || (p[i] == p[j])){
i++;
j++;
next[i] = j;
}/*if*/
else{
j = next[j];
}/*else*/
}/*while*/
}/*get_next*/
int kmp(char s[], char p[], int pos, int next[]) {
/*KMP アルゴリズム */
int i, j, slen, plen;
i = pos;
j = 0;
slen = strlen(s);
plen = strlen(p);
while((i < slen) && (j < plen)){
if((j == -1) || (s[i] == p[j])){
i++;
j++;
}
else
{
j = next[j];
}
}/*while*/
if(j >= plen) {
return (i-plen);
}/*if*/
else {
return -1;
}/*else*/
}/*kmp*/
int index(char s[], char p[], int pos){
/* インデックスマッチング法 */
int i, j, slen, plen;
i = pos;
j = 0;
slen = strlen(s);
plen = strlen(p);
while((i < slen) && (j < plen)){
if((s[i] == p[j])){
i++;
j++;
}/*if*/
else{
i = i-j+1;
j = 0;
}/*else*/
}/*while*/
if(j >= plen) {
return (i-plen);
}
else {
return -1;
}
}/*index*/
void main(){
char s [] = "acbaabcaacabaabaabcacaabc"; /* テスト文字列 */
char p[] = "abaabca";
int next[50];
getNext(p, next);
printf("found index at %dn", kmp(s, p, 0, next));
printf("found index at %dn", index(s, p, 0));
}/*main*/
KMP アルゴリズムは kmp () 関数であり、INDEX アルゴリズムは index () 関数です。皆さんはお気づきかと思いますが、KMP アルゴリズムは追加の配列を計算する必要があります。これが精髓であり、効率が向上し、効率が 1 桁向上します。皆さんはこのような効率向上の結果を知っていると思いますが、最悪の場合には多くのスペースを無駄にする可能性があります。さて、アルゴリズムの提供は以上です。アルゴリズムの部分が理解できない場合は、直接コメントを残すか、私に連絡することができます。
附：ネットワークからの KMP マッチングアルゴリズム C++ 実装アルゴリズム、http://www.chinaitpower.com/A/2003-01-04/45995.htmlからの引用です。著者には謝罪しますが、参考のために借用させていただきます。個人的には純粋な C が好きで、最近はあまり C++ を使用していません。