(文字列)KMPアルゴリズム

しばらくサボってて申し訳ないです。
別にサボってたわけではなく。仕事がうまくいかなかったり、BIOSのサービスコールやIA32、16を勉強したりとより実装指向な話題に陶酔していました。こちらも近日活動公開できればなんですがどうも、趣味の中でも一番楽しんでいる分野なのでこれから

でも「初志貫徹」ですよね。うまくいかないこともあります。話が変わりますがすごい小さい頃から野球をはじめたイチロー選手ですら10球中4球しか打てないんですもの。自分も10個問題があったら3つくらい完答できればあとは部分的な解でも許されると思います。ましてや頭がいい人にはすぐにはかないません。

というわけで文字列照合アルゴリズムの続きを書きます。まず入る前に前回の復習をしてください。

KMP(Knuth-Morris-Pratt)アルゴリズムです。詳しい資料は
http://www.mm.ics.saitama-u.ac.jp/~ohsawa/Lect/dstr/13.pdfにあります。

概略の説明。

今まで説明した単純な文字列照合はある位置にパターンを置いて比較したとき得られる情報を重っ分に利用しないでしててしまうことに問題がある。そこであらかじめパターンとなる文字列についてその規則性を記録することにより、参照をする文字のジャンプ力を高めることができるのである。この考え方は後述するBMアルゴリズムにも応用される。KMPアルゴリズムは計算量がパターンの情報量に比例しないためO(2n)となる。

今回は上記のurlで述べられているソースではなく、岩波講座ソフトウエア科学3のほうを参照し記述した。

//KMP.c
#include
#include

#define N 21 //textの長さ
#define M 7 //patternの長さ

char text="ababdeabababbabababab";
char pattern="abababa";
int next[M];

void kmpinit(void)//まず、パターンの規則性を調べる
{
int t,j;
t=-1;
next[0]=0;//はじめはジャンプの値は1なのでデフォルト値として0をいれる
for(j=1;j<=M;j++)
{
while(t>0&&pattern[j-1]!=pattern[t])
t=next[t];
t++;
if(pattern[j]!=pattern[t])
next[j]=t;
else
next[j]=next[t];
}
}

int kmp(void)
{
int i,j;
i=j=0;
while(i0 && text[i]!=pattern[j])
j=next[j];
i++;
j++;
}
if(j0)
printf("探している文字は%d番目\n",i);
else
printf("no matched\n");
return 0;
}