C++実現文字列マッチングKMPアルゴリズム
13927 ワード
文書ディレクトリ 1. 概要 2. コード実装 3. コードテスト 1.概要
Kmpアルゴリズムの紹介と思想は以下の2つの文章を参照する:文字列マッチングKMPアルゴリズムアルゴリズム)分かりやすい文字列マッチングKMPアルゴリズムとnext値アルゴリズムを求める
2.コード実装
3.コードテスト
Kmpアルゴリズムの紹介と思想は以下の2つの文章を参照する:文字列マッチングKMPアルゴリズムアルゴリズム)分かりやすい文字列マッチングKMPアルゴリズムとnext値アルゴリズムを求める
2.コード実装
int cTest::findstr1(const char *src, const char *des)
{
int srlen = strlen(src);
int delen = strlen(des);
int i = 0, j = 0, k = 0;
for (int i = 0; i <= srlen - delen; i++)
{
/* code */
for (k = i, j = 0; j < delen; ++k, ++j)
{
/* code */
if (src[k] != des[j])
break;
}
if (j >= delen)
return i;
}
return -1;
}
void cTest::subNext_kmp(const char *des, int *next)
{
next[0] = -1;
int i = 0, k = -1;
while (des[i] != '\0')
{
/* code */
if (k == -1 || des[k] == des[i])
next[++i] = ++k;
else
k = next[k];
}
}
int cTest::findstr2(const char *src, const char *des, int* next)
{
int slen = strlen(src);
int dlen = strlen(des);
int i = 0, j = 0;
while (i < slen && j < dlen)
{
/* code */
if (j==-1 || src[i] == des[j])
{
++i;
++j;
}
else
/* code */
j = next[j];
}
if (des[j] == '\0')
return i - j;
return -1;
}
3.コードテスト
int main(int argc, char* argv[])
{
char s[] = "abcabaaaabaabcac";
char p[] = "abaabcac";
cout << ctestptr.findstr1(s, p) << endl;
//shared_ptr next(new int[sizeof(p)],[](int* p){delete[] p;});
int *next = (int *)malloc(sizeof(int) * sizeof(p));
ctestptr.subNext_kmp(p, next);
for (int i = 0; i < strlen(p); ++i)
cout << next[i];
cout << endl;
cout << ctestptr.findstr2(s, p, next) << endl;
free(next);
}