HDU 1711-Number 시퀀스-KMP 알고리즘(템 플 릿)
이 문자열 이 일치 하 는 템 플 릿 문제;
사실 KMP 알고리즘 은 이해 하기 쉽 지만 처음 만 났 을 때 그 가 어떻게 왔 는 지 이해 하 는 next 배열 이 힘 들 수 있 습 니 다.제 가 잠시 개괄적 으로 말씀 드 리 겠 습 니 다.
우리 가 조회 하고 자 하 는 문자열 에 대해 서 는 먼저 접두사 와 접 두 사 를 처리 하여 next 배열 에 저장 합 니 다.예 를 들 면 이 숫자.
b[]= 1 2 3 4 1 2 4
next= -1 0 0 0 0 1 2 우 리 는-1 로 시작 을 표시 합 니 다.next=1 은 접두사 와 접두사 가 한 글자 만 일치 하 는 것 을 나타 낸다.우 리 는 next 로 저장 한 후,
우리 가 제시 한 찾기 배열 a[]와 일치 할 때 선형 일치 에 도달 할 수 있 습 니 다.왜 요?문자열 이 일치 하면 앞에서 처음 일치 하 는 위치 로 돌아 가지 않 아 도 되 기 때 문 입 니 다.+1 부터 일치 하기 시작 합 니 다.
우 리 는 사전에 a[]를 한 번 찾 았 기 때문에 접두사 와 접두사 가 같은 개 수 를 찾 아 냈 다.이렇게 하면 우 리 는 바로 뒤로 이동 할 수 있다.
이렇게 하면 우 리 는 시간의 복잡 도가 O(n+m)에 도달 할 수 있다.코드 도 복잡 하지 않 고 효율 도 좋 기 때문에 문자열 일치 에 있어 KMP 는 자주 사용 되 는 것 입 니 다.
KMP 의 과정 에 대한 상세 한 설명 이 담 긴 블 로 그 를 추천 합 니 다.링크:http://kb.cnblogs.com/page/176818/
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200005;
int a[N*10],b[N],Next[N];
void Get_Next(int m) // Next ；
{
int i=0,j=-1;
Next[0]=-1;
while(i<m){
if(j==-1||b[i]==b[j]) Next[++i]=++j;
else j=Next[j];
}
return;
}
int KMP(int n,int m) // KMP ；
{
int i=0,j=0;
while(i<n){
if(a[i]==b[j]){
if(j==m-1) return i-m+2;
i++,j++;
}else{
j=Next[j];
if(j==-1) i++,j=0;
}
}
return -1;
}
int main()
{
int t,m,n;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<m;i++) scanf("%d",&b[i]);
if(m>n) printf("-1
");
else{
Get_Next(m);
printf("%d
",KMP(n,m));
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 2442 SequenceSequence Time Limit: 6000MS Memory Limit: 65536K Total Submissions: 6120 Accepted: 1897 Description Given m sequences, e...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
