문자열 패턴 일치
1. 소박 모드 매 칭 알고리즘
이 알고리즘 은 가장 간단 한 일치 알고리즘 입 니 다. 알고리즘 사상 은 다음 과 같 습 니 다. 메 인 문자열 s 의 첫 번 째 문자 부터 패턴 문자열 t 의 첫 번 째 문자 와 비교 하고 같 으 면 후계 문 자 를 계속 비교 합 니 다.그렇지 않 으 면 메 인 문자열 의 다음 문자 부터 패턴 문자열 의 첫 번 째 문자 와 다시 비교 합 니 다. 패턴 문자열 t 의 모든 문자 가 메 인 문자열 s 의 문자 서열 과 같 을 때 까지 일치 합 니 다. 패턴 문자열 t 의 첫 번 째 문자 와 같은 문자 가 메 인 문자열 s 에 있 는 위 치 를 되 돌려 줍 니 다.그렇지 않 으 면 일치 하지 않 으 면 - 1 로 돌아 갑 니 다.예 를 들 어 메 인 문자열 s 는 ababcabcacbab 이 고 패턴 문자열 t 는 abcacb 이 며 일치 하 는 과정 은 다음 과 같 습 니 다.
제1회: ababcabcacbab i=3
abc j=3 일치 실패
제 2 회: ababcabcacbab i=2
a j=1 일치 실패
제3 회: ababcabcacbab i=7
abcac j=5 일치 실패
제4 회: ababcabcacbab i=4
a j=1 일치 실패
제5 회: ababcabcacbab i=5
a j=1 일치 실패
제6 회: ababcabcacbab i=11
abcacb j=6 일치 성공
위 에서 보 듯 이 6 번 째 일치 할 때 s 에서 t 를 찾 았 습 니 다. 이 때 일치 하 는 데 성공 하여 t 첫 번 째 문자 와 같은 문자 가 s 에 나타 난 위 치 를 되 돌려 줍 니 다.알고리즘 구현 은 다음 과 같 습 니 다.
// ： s, t
int index(char *s, char *t)
{
int i = 0, j = 0;
while(i < strlen(s) && j < strlen(t))
{
if(s[i] == t[j])
{
i++; j++;
}
else // s t
{
i = i - j + 1;
j = 0;
}
}
if(j >= strlen(t)) //
return i - j + 1;
else //
return -1;
}상기 분석 을 통 해 우 리 는 이 알고리즘 의 시간 복잡 도 는 O (mn) (그 중에서 n 을 위주 로 하 는 길이, m 를 모델 로 하 는 길이) 라 는 것 을 알 수 있다.메 인 문자열 과 패턴 문자열 이 비교적 길 었 을 때 일치 하 는 데 걸 리 는 시간 도 우리 가 받 아들 일 수 없 는 것 일 수 있 습 니 다. 현재 하드웨어 가 선진 적 이지 만 이 알고리즘 에 대한 개선 이 필요 합 니 다. 다음은 이 알고리즘 에 대한 개선 인 KMP 알고리즘 을 소개 합 니 다.
2. KMP 알고리즘
KMP 알고리즘 은 D. E. Knuth, V. R. Pratt 와 J. H. Morris 가 동시에 발 견 했 기 때문에 이 알고리즘 을 크 누 트 - 모 리 스 - 프 라 트 알고리즘 이 라 고 부 르 며 KMP 알고리즘 이 라 고 부른다.소박 한 알고리즘 의 시간 복잡 도가 높 은 이 유 는 역 추적 이 존재 하기 때 문 입 니 다. KMP 알고리즘 의 개선 점 은 바로 패턴 문자열 을 예비 처리 하고 일치 하 는 과정 에서 이러한 역 추적 을 없 애고 일치 효율 을 향상 시 키 는 것 입 니 다.따라서 KMP 알고리즘 은 패턴 문자열 에 대한 사전 처리 가 관건 이 고 패턴 문자열 에 대한 처 리 는 메 인 문자열 과 무관 합 니 다.
우 리 는 먼저 아래 의 예 를 보 자.만약 에 A = "abababaababacb", B = "ababacb", KMP 가 어떻게 일 하 는 지 봅 시다.우 리 는 두 개의 지침 i 와 j 로 각각 A [i - j + 1. i] 와 B [1. j] 가 완전히 같다 고 표시 했다.즉, i 는 계속 증가 하고 i 의 증가 에 따라 j 는 상응 하 게 변화 하 며 j 는 A [i] 로 끝 나 는 길 이 를 j 로 하 는 문자열 이 B 문자열 의 앞 j 문자 (j 는 당연히 클 수록 좋다) 와 일치 하 는 것 을 만족 시 키 므 로 지금 은 A [i + 1] 과 B [j + 1] 의 관 계 를 검증 해 야 한다.A [i + 1] = B [j + 1] 시 i 와 j 가 각각 1 을 추가 합 니 다.언제 j = m 가 되 었 습 니까? 우 리 는 B 가 A 의 하위 꼬치 (B 꼬치 가 이미 완성 되 었 습 니 다) 라 고 말 하고 이때 의 i 값 에 따라 일치 하 는 위 치 를 계산 할 수 있 습 니 다.A [i + 1] < > B [j + 1] 에서 KMP 의 전략 은 j 의 위 치 를 조정 하 는 것 (j 값 을 줄 이 는 것) 입 니 다.i = j = 5 시의 상황 을 살 펴 보 자. i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1, 2, 3, 4, 5, 6, 7 이때 A [6] < > B [6].이것 은 이때 j 가 5 와 같 을 수 없다 는 것 을 나타 낸다. 우 리 는 j 를 그것 보다 작은 값 j 로 바 꿔 야 한다.제 이 가 얼마 일 까요?곰 곰 이 생각해 보 니 j '는 B [1. j] 의 머리 j' 자모 와 끝 j '자 모 를 완전히 같 게 해 야 한 다 는 것 을 알 게 되 었 다.이 제 이 는 당연히 크 면 클 수록 좋다.여기 서 B [1. 5] = "ababa" 는 첫 세 글자 와 끝 세 글자 가 모두 "aba" 입 니 다.그리고 새로운 j 가 3 일 때 A [6] 는 마침 B [4] 와 같다.그래서 i 는 6 이 되 었 고 j 는 4 가 되 었 다. i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1, 2, 3, 4, 5, 6, 7 위의 이 예 에서 우 리 는 새로운 j 가 얼마나 취 할 수 있 는 지 i 와 상 관 없 이 B 꼬치 와 만 관련 이 있다 는 것 을 알 수 있다.우 리 는 이러한 배열 next [j] 를 미리 처리 할 수 있 습 니 다. B 배열 의 j 번 째 자모 와 일치 하고 j + 1 번 째 자모 가 일치 하지 않 을 때 새로운 j 는 최대 얼마 입 니까?next [j] 는 모든 만족 B [1. next [j] = B [j - next [j] + 1. j] 의 최대 치 일 것 이다.그리고 A [7] = B [5], i 와 j 가 각각 1 씩 증가한다.이때, 또 A [i + 1] < > B [j + 1] 의 상황 이 나 타 났 다. i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1, 2, 3, 4, 5, 6, 7 은 next [5] = 3 이기 때문에 새로운 j = 3: i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1, 2, 3, 4, 5, 6, 7 이때 새로운 j = 3 은 A [i + 1] = B [j + 1] 를 만족 시 키 지 못 한다. 이때 우 리 는 j 값 을 다시 줄 이 고 j 를 next [3] 로 다시 업데이트 한다. i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1, 2, 3, 4, 5, 6, 7.이때 A [8] 는 B [j + 1] 와 같 지 않 았 다.이렇게 하면 j 는 반드시 P [1], 즉 0 으로 줄 여야 한다. i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 0 1, 2, 3, 4, 5, 6, 7 드디어 A [8] = B [1], i 는 8, j 는 1 로 바 뀌 었 다.사실 j 가 0 이 되 어도 A [i + 1] = B [j + 1] (예 를 들 어 A [8] = 'd' 시) 를 만족 시 키 지 못 할 수도 있다.따라서 정확 한 말 은 j = 0 이 되면 우 리 는 i 값 을 증가 하지만 j 가 A [i] = B [1] 가 나타 날 때 까지 무시 한 다 는 것 이다.배열 next 의 코드 는 다음 과 같 습 니 다.
int next[100];
void getnext(char *b)
{
int i = 1, j = 0;
next[1] = 0;
while(i <= strlen(b))
{
if(j == 0 || b[i - 1] == b[j - 1])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
}next 배열 을 계산 한 후에 위의 설명 에 따라 우 리 는 KMP 알고리즘 의 구체 적 인 실현 을 쉽게 쓸 수 있 습 니 다.
int kmp(char *a,char *b)
{
int i = 1, j = 1; //i ，j
while(i <= strlen(a) && j <= strlen(b))
{
if(j == 0 || a[i - 1] == b[j - 1])
{
i++;
j++;
}
else
j = next[j];
}
if(j > strlen(b))
return i - strlen(b);
else
return 0;
}KMP 의 구체 적 인 실현 과정 과 next 의 배열 을 구 하 는 과정 은 비슷 하 다.KMP 알고리즘 을 이용 한 패턴 일치 시간 복잡 도 는 O (n) 입 니 다.소박 한 매 칭 알고리즘 에 비해 시간 복잡 도 는 크게 향상 되 었 다.
문자열 일치 에 대한 연 구 는 현재 언급 한 두 가지 방법 을 제외 하고 접미사 트 리 와 같은 다른 방법 도 있 습 니 다. 이런 방법 들 은 모두 예비 처 리 를 이용 하여 선형 시간 내 에 문자열 일치 문 제 를 해결 할 수 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
