[알고리즘] 문자열 의 간단 한 패턴 일치
대상 의 일치 하 는 위 치 를 찾기 위 한 연산 을 패턴 일치 (Pattern matching) 라 고 합 니 다.
단순 모드 매 칭 알고리즘 BF 알고리즘
[알고리즘 사상]
메 인 문자열 T 의 첫 번 째 pos 문자 와 패턴 P 의 첫 번 째 문 자 를 비교 하고 같 으 면 후속 문 자 를 계속 비교 합 니 다.다 르 지 않 으 면 메 인 문자열 T 의 다음 문자 (pos + 1) 부터 P 의 첫 번 째 문자 와 비교 합 니 다.
주 문자열 T 의 연속 하위 문자열 문자 시퀀스 가 패턴 P 와 같 을 때 까지.반환 값 은 T 에서 P 와 일치 하 는 하위 시퀀스 의 첫 번 째 문자 의 번호 입 니 다. 즉, 일치 하 는 데 성 공 했 습 니 다.
그렇지 않 으 면 일치 실패, 반환 값 - 1.코드 는 다음 과 같 습 니 다:
1 int NaiveStrMatching(string T, string P)
2 {
3 int i = 0, j = 0;
4 int plen = P.length();
5 int tlen = T.length();
6 if(tlen < plen) return -1;
7 while(i < tlen && j < plen)
8 {
9 if(T[i] == P[j])
10 {
11 i ++;
12 j ++;
13 }
14 else
15 {
16 i = i - j + 1; //
17 j = 0;
18 }
19 }
20 if(j >= plen) return i - j; //
21 else return -1;
22 }알고리즘 분석:
목표 T 의 길 이 를 n 으로 설정 하고 모드 P 의 길 이 는 m 이 며 최 악의 경우 비교 횟수: (n - m + 1) * m
대부분의 경우 m 는 n 보다 훨씬 작 기 때문에 알고리즘 의 최 악의 시간 복잡성 은 O (n * m) 이다.복잡 도가 높 고 효율 이 낮다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
