[하 이 호 한번]3 주차 KMP 알고리즘.

제목 1:KMP 알고리즘
제목http://hihocoder.com/contest/hiho3/problem/1
[제목 해독]
KMP 알고리즘 의 기본 사용 중 하나 입 니 다.계수 기능 이 추가 되 었 습 니 다.
KMP 알고리즘 의 핵심 사상 은 일치 실패 시 패턴 문자열 의 역 추적 수 를 줄 여 일치 횟수 를 줄 이 는 것 이다.이때 거 슬러 올 라 갈 때 next 배열 을 사용 합 니 다.
next 배열 참조:http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html주의해 야 할 것 은 여기에 수학 귀납법 이 사용 되 었 다 는 것 이다.즉:
가설:정의 에 따라 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]
next 배열 의 구 해 는 서로 다른 패턴 문자열 로 볼 수 있 습 니 다.그 중 하 나 는 원본 문자열 이 고 다른 하 나 는 패턴 문자열 로 일치 하 며 실 패 는 역 추적 합 니 다.
[디 테 일 작성]
(1)KMP 알고리즘 의 주체 비교 부분 을 이해 하려 면 먼저 BF 알고리즘 을 실현 하 는 것 이 가장 일반적인 폭력 적 인 일치 입 니 다.다음 과 같다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char ori[1000005];
char par[10005];
int next[10005];

int main()
{
	int t;
	scanf("%d", &t);
	long olen;
	int plen;
	int ans;
	while(t--)
	{
		ans = 0;
		memset(ori, 0, sizeof(ori));
		memset(par, 0, sizeof(par));
		memset(next, 0, sizeof(next));
		
		scanf("%s", par);
		scanf("%s", ori);
		
		olen = strlen(ori);
		plen = strlen(par);
		
		for(long i=0; i<olen; i++)
		{
			long j = i;
			int k = 0;

			while(ori[j] == par[k])
			{
				j++;
				k++;
				if(k >= plen) break;
			}

			if(k>=plen) ans++;
		}
		printf("%d
", ans);
	}
	return 0;
}

이것 을 대조 해서 KMP 의 테마 가 일치 하 는 것 을 쓰 면 for 의 첫 번 째 while 를 이해 할 수 있 습 니 다.원본 문자열 과 패턴 문자열 의 첫 번 째 일치 점 을 찾기 위해 서(반드시 패턴 문자열 의 첫 번 째 문자 가 아 닙 니 다).
(2)KMP 에서 일치 하지 않 으 면 거 슬러 올 라 가(절대 사용 하지 않 음-)일률적으로 k=next[k]를 사용 하고 k--를 사용 하지 않 습 니 다.첫 번 째 를 거 슬러 올 라 가면 그 후에 일치 하지 않 으 면 일치 하 는 것 을 찾 거나 끝까지 거 슬러 올 라 갈 수 있다.
(3)주의 하 세 요!KMP 알고리즘 은 패턴 문자열 과 원본 문자열 의 길이 가 모두 1 일 때의 상황 을 단독으로 고려 해 야 합 니 다!횟수 next 배열 은 값 이 하나 밖 에 없습니다-1;
(4)이 문 제 는 KMP 가 일치 하 는 계수 기능 이기 때문에 ABABA 에 두 개의 ABA 가 누락 되 지 않도록 원본 문자열 의 한 글자 스 캔(for 순환)이 필요 합 니 다.
(5)나머지 세부 사항 은 코드 주석 에 적 습 니 다...어렵 습 니 다.양식 으로 적어 주세요.
[AC 코드]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char ori[1000005];
char par[10005];
int next[10005];
int t, plen;
long olen, ans;

void get_next(int len)
{
	next[0] = -1;
	int j = 0;
	int k = -1;
	while(j < len)
	{
		//            ，         
		if(k==-1 || par[j] == par[k])	
		{
			//     j      
			next[j+1] = k + 1;
			j++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}

int main()
{
	scanf("%d", &t);
	while(t--)
	{
		ans = 0;
		scanf("%s", par);
		scanf("%s", ori);
		
		plen = strlen(par);
		olen = strlen(ori);
		
		if(olen==1 && plen==1)
		{
			if(ori[0] == par[0])
				ans = 1;
			else
				ans = 0;
			
			printf("%d
", ans);
			continue;
		}
    
		get_next(plen);
		int j = 0;
		for(long i=0; i<olen; i++)
		{
			// while   ：               
			// j>=1    next[j]=-1，       olen=plen=1 
			while(ori[i] != par[j] && j>=1)
			{
				j = next[j];
			}
			
			if(ori[i] == par[j])
			{
				j++;
			}
			//             ，i    ++ 
//			else
//			{
//				j = next[j];
//			}
			
			if(j >= plen)
			{
				ans++;
				//          ，         
				j = next[j];
			}
		}
		printf("%d
", ans);
	}
	return 0;
}