C 언어 소박 모드 일치 알고리즘 인 스 턴 스 코드

1.문자열 의 패턴 이 일치 하 는 것 은 무엇 입 니까?
문자열 모드 일치:주 문자열 에서 패턴 문자열 과 같은 하위 문자열 을 찾 아 그 위 치 를 되 돌려 줍 니 다.
주의:
① 하위 꼬치-메 인 꼬치 의 일부분 은 반드시 존재 한다.
② 패턴 문자열-메 인 문자열 에서 찾 을 수 있 는 것 은 아니다.
 
2.소박 모드 매 칭 알고리즘

메 인 문자열 의 길 이 는 n 이 고 패턴 문자열 의 길 이 는 m 입 니 다.
소박 모드 매 칭 알고리즘:메 인 문자열 의 모든 길이 가 m 인 하위 문자열 을 패턴 문자열 과 순서대로 비교 하여 완전히 일치 하 는 하위 문자열 을 찾 거나 모든 하위 문자열 이 일치 하지 않 을 때 까지 합 니 다.
최대 대비 n-m+1 문자열
(1)배열 아래 표 시 를 통 해 소박 한 패턴 일치 알고리즘 을 실현 합 니 다.

현재⼦串 일치 에 실패 하면 주 串 포인터 i 는 아래⼀⼦串 의 제⼀개 위 치 를 가리 키 고,모드 串 포인터 j 는 모드 串 의 제⼀개 위치 로 돌아간다.
만약 에j > T.length그러면 현재*12070°문자열 이 성공 적 으로 일치 하고 현재*12070°문자열 의 위 치 를 되 돌려 줍 니 다i - T.length

int Index(SString S, SString T){
	int i=1,j=1;
	while(i <= S.length && j<=T.length){
		if(S.ch[i]==T.ch[j]){
			++i;
			++j;	//        
		}
		else{
			i=i-j+2;
			j=1;	//          
		}
	}
	if(j > T.length)
		return i-T.length;
	else
		return 0;
}

(2)시간 복잡 도
메 인 스 트 링 을 n 으로 설정 하고 모드 스 트 링 을 m 로 설정 하면
①、최 악의 시간 복잡 도=O(nm)
②、최 적 시간 복잡 도=O(n)1.최 악의 시간 복잡 도 O(nm)

최 악의 경우,모든 문자열 은 전체 12112°m 문자,총 n-m+1 개의 문자열,복잡 도=O(n-m+1)m=O(nm)
n>>m
2.가장 좋 은 시간 복잡 도 O(n)

가장 좋 은 경우,모든 문자열 의 첫 번 째 문 자 는 일치 하지 않 습 니 다.모두 n-m+1 개의 문자열,복잡 도=O(n-m+1)=O(n)
n>>m
총결산
C 언어 소박 모드 매 칭 알고리즘 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 C 언어 소박 모드 매 칭 알고리즘 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!