KMPアルゴリズムの詳細と各種応用

7307 ワード

KMPアルゴリズム详细解:KMPアルゴリズムをKMPアルゴリズムと呼ぶのは、このアルゴリズムが3人で共同で提案されたため、3人の名前の头文字をアルゴリズムの名前として取ったからです.実はKMPアルゴリズムとBFアルゴリズムの違いは、KMPアルゴリズムがポインタiの遡及問題を巧みに解消し、次回jに一致する位置を特定するだけで、問題の複雑さをO(mn)からO(m+n)に低下させることにある.KMPアルゴリズムでは,マッチングが成功しない場合に次のマッチング時jの位置を決定するためにnext[]配列を導入し,next[j]の値はP[0...j-1]の最長接尾辞の長さが同じ文字列の接頭辞に等しいことを示す.next[]配列の定義は、1)next[j]=-1 j=02)next[j]=max k:00の場合、P[0...k-1]=P[j-k,j-1]を表すため、KMPアルゴリズムの考え方は、マッチングプロセスにおいて、不一致が発生した場合、next[j]>=0であれば、ターゲット列のポインタiは変わらず、モード列のポインタjをnext[j]の位置に移動してマッチングを継続する.next[j]=-1の場合、iを1ビット右にシフトし、jを0にして比較を続行します.コードは次のように実装されます.

int KMPMatch(char *s,char *p)
{
    int next[100];
    int i , j;
    i = 0;
    j = 0;
    getNext(p , next);
    while(i < strlen(s))
    {
        if(j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];       //     i   
        }
        if(j == strlen(p))
            return i - strlen(p);
    }
    return -1;
}

したがってKMPアルゴリズムの鍵はnext[]配列の値を求めることにある.すなわち、モード列の各位置における最長接尾辞と接頭辞の同じ長さを求めることである.next[]配列の値を求めるには2つの考え方があり、第1の考え方は繰返しの思想で計算することであり、もう1つは直接解くことである.
1、プッシュの考え方によって:
定義next[0]=−1に基づいて、next[j]=k、すなわちP[0...k−1]=P[j−k,j−1]
1)P[j]==P[k]の場合、P[0..k]==P[j-k,j]があり、next[j+1]=next[j]+1=k+1であることは明らかである.
2)P[j]!=P[k]は,マッチングに失敗した場合,k値がどのように移動するか,明らかにk=next[k]というパターンマッチングの問題と見なすことができる.
そのため、次のように実現できます.

void getNext(char *p,int *next)
{
    int j,k;
    next[0] = -1;
    j = 0;
    k = -1;
    while(j < strlen(p) - 1)
    {
        if(k == -1 || p[j] == p[k])    //      ,p[j]==p[k]
        {
            j++;
            k++;
            next[j] = k;
        }
        else                   //p[j]!=p[k]
            k = next[k];
    }
}

、直接解法

void getNext(char *p,int *next)
{
    int i , j , temp;
    for(i = 0 ; i < strlen(p) ; ++i)
    {
        if(i == 0)
        {
            next[i] = -1;     //next[0]=-1
        }
        else if(i == 1)
        {
            next[i] = 0;      //next[1]=0
        }
        else
        {
            temp = i - 1;
            for(j = temp ; j > 0 ; --j)
            {
                if( equals(p , i , j) )
                {
                    next[i] = j;   //     k 
                    break;
                }
            }
            if(j == 0)
                next[i] = 0;
        }
    }
}
 
bool equals(char *p,int i,int j)     //  p[0...j-1] p[i-j...i-1]     
{
    int k = 0;
    int s = i - j;
    for( ; k <= j - 1 && s <= i - 1 ; k++ , s++)
    {
        if(p[k] != p[s])
            return false;
    }
    return true;
}

http://poj.org/problem?id=2406
1つの文字列を指定し、同じサブストリングが重複しない接続構成が最大何個あるかを尋ねます.
KMPのnext配列アプリケーション.ここでは主に,このようなサブストリングがあるかどうか,サブストリングの個数をどのように判断するかである.
abababaであれば,それ自体を除いてサブストリングが条件を満たしていないことは明らかである.そのnext配列を解析すると、next[7]=5、next[5]=3、next[3]=1、すなわちstr[2..7]はbaサブストリング接続で構成できるが、このような状況をどのように否定するのか.簡単です.このサブストリングが条件を満たすと、len%sublenは必ず0になります.sunlenは、上記の解析からlen−next[len]として得ることができる.
サブストリングが先頭と末尾が接するため、len/sublenはsubstrの個数である.
L%(L-next[L])=0,n=L/(L-next[L]),else n=1

#include<iostream>
#include<cstdio>
using namespace std;

char pattern[1000002];
int next[1000002];

/*
kmp  ，          next   
next[j] = k,   p0pk-1 == pj-kpj-1,    k          
*/
void get_nextval(const char* pattern)
{
	int i=0,j=-1;
	next[0]= -1;
	while(pattern[i] != '\0')
	{
		if(j== -1 || pattern[i]== pattern[j] )     //pattern[i]         ，pattern[j]         
		{
			++i;
			++j;
			if(pattern[i] != pattern[j])
				next[i]=j;
			else
				next[i]=next[j];
		}
		else
			j=next[j];    // j    ， j   
	}
}//get_nextval

int main(void)
{
	int len;
	while(scanf("%s",pattern)!=EOF)
	{
		if(pattern[0]=='.')
			break;
		len=strlen(pattern);

		get_nextval(pattern);			
		
		if(len%(len-next[len])==0)
			printf("%d
",len/(len-next[len]));
		else
			printf("1
");
			
	}
	return 0;
}

http://poj.org/problem?id=1961
文字列Aを定義し、Aが最大n個の同じ文字列sで接続されている場合、A=s^n、例えば「aaa」=「a」^3、「abab」=「ab」^2「ababa」=「ababa」^1は文字列Aを与え、その文字列のすべての接頭辞のうちどれだけの接頭辞SA=s^n(n>1)が条件を満たす接頭辞の長さと対応するnを出力するかを求める
例えばaaa接頭辞aaの長さが2であり、2つの'a'からなる接頭辞aaaの長さが3であり、3つの「a」からなる
分析:KMPある長さLの接頭辞が控訴条件に合致する場合、1.next[L]!=0(next[L]=0の場合は文字列が元の文字列であり、条件に合致しない).L%(L-next[L])=0(このとき文字列の長さはL/next[L])
2:str[0]....str[next[L]-1]=str[L-next[L]-1]...str[L-1] =》str[L-next[L]-1] = str[L-next[L]-1+L-next[L]-1] = str[2*(L-next[L]-1)]; S=L-next[L]-1とする.str[0]=str[s]=str[2*s]=str[3*s]...str[k*s]は、すべてのi%s=0に対して、s[i]=s[0]同理があり、str[1]=str[s+1]=str[2*s+1]... str[j]=str[s+j]=str[2*s+j].... 以上、L%S=0であれば、Lはstr[0]...str[s-1]の同じ文字列からなり、全長Lであり、文字列長SL=s-0+1=L-next[L]であり、サイクル数L/SLであるため、1より大きい接頭辞については、上記条件に合致する限り、答えの1つである

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

char pattern[1000002];
int next[1000002];

/*
kmp  ，          next   
next[j] = k,   p0pk-1 == pj-kpj-1,    k          
*/
void get_nextval(const char* pattern)
{
	int i=0,j=-1;
	next[0]= -1;
	while(pattern[i] != '\0')
	{
		if(j== -1 || pattern[i]== pattern[j] )
		{
			++i;
			++j;
			next[i]=j;
		}
		else
			j=next[j];
	}
}//get_nextval

int main(void)
{
	int i,len,n,j=1;
	while(scanf("%d",&n)!=EOF)
	{
		if(!n)
			break;
		scanf("%s",pattern);
		len=strlen(pattern);

		get_nextval(pattern);
	
		printf("Test case #%d
",j++);
		for(i=2;i<=len;i++)
		{
			if(i%(i-next[i])==0 && i/(i-next[i])>1)
				printf("%d %d
",i,i/(i-next[i]));
		}
		printf("
");
			
	}
	return 0;
}

http://poj.org/problem?id=2752文字列Aを与えて、Aがどれだけの接頭辞が同時に接尾辞であることを求めて、小さいから大きいまでこれらの接頭辞の長さを出力します.
解析:KMPは長さlenの文字列についてnextの定義で知られている:A[0]A[1]...A[next[len]-1]=A[len-next[len]]...A[len-1]このときA[0]A[1]...A[next[len]-1]は条件を満たす接頭辞であるA[0]A[1]...である.A[next[next[len]]-1] = A[len-next[next[len] - next[next[len]]]...A[next[len]-1]だから、A[0]A[1]....A[next[next[len]]-1]も条件を満たす接頭辞であるためlen=>next[len]=>next[next[len]....=>あるnext[]が0になるまで合法的な答えであり、最初の単語が同じである場合、答えであることに注意してください.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

char pattern[400002];
int next[400002];

/*
kmp  ，          next   
next[j] = k,   p0pk-1 == pj-kpj-1,    k          
*/
void get_nextval(const char* pattern)
{
	int i=0,j=-1;
	next[0]= -1;
	while(pattern[i] != '\0')
	{
		if(j== -1 || pattern[i]== pattern[j] )
		{
			++i;
			++j;
			next[i]=j;
		}
		else
			j=next[j];
	}
}//get_nextval

int main(void)
{
	int i,len,n;
	vector<int>ans;
	while(scanf("%s",pattern)!=EOF)
	{
		ans.clear();
		len=strlen(pattern);
		get_nextval(pattern);
		n=len;
		while(n)
		{
			ans.push_back(n);
			n=next[n];
		}
		if(pattern[0]==pattern[n-1])   //  、      
			ans.push_back(1);

		i=ans.size()-1;
		for(;i>0;i--)
			printf("%d ",ans[i]);
		printf("%d
",ans[0]);
	}
	return 0;
}

OpenCVベースLBPアルゴリズム(OpenCV 1.0バージョン)

3つの整数を入力し、プログラムにデータを小さい順にx y zに入れて出力するように要求します(C)