자료구조 | String

21/06/11 - 14 자료구조 및 실습;;
(주말에 놀았음 ㅎ)
Basic - 6.String

String
0혹은 그이상의 character들의 무한한 집합

char의 경우 한 바이트, char가 string으로 저장되면 끝나는 부분에 null point로 표시

pattern matching

string: missy the monkey is missing
Pattern: monkey

end index부터 먼저 체크하는 방식으로 진행

int nfind (char *string, char *pat)
{
 int i, j, start = 0;
 int lasts = strlen(string)-1, lastp = strlen(pat)-1;
 int endmatch = lastp;
 for (i = 0; endmatch<=lasts; endmatch++, start++){ 
 	if (string[endmatch] == pat[lastp]) { 
// if문에 해당하면 밑에 for 실행, 해당하지 않으면 위의 for문 1증가
 		for (j = 0, i = start; j<lastp && string[i] == pat[j]; i++, j++)
 		if (j == lastp)
 			return start;
            //start의 위치부터 시작해서 pat이 맞았기 때문에 start 값을 리턴해줌
      }
   }
 return -1;
 }

i = string에서 한글자씩 가리키는 위치
j = pattern에서 ''
lastp = pattern의 끝위치( strlen(pat)-1 )
lasts = string의 끝위치 ( strlen(string)-1)

KMP 알고리즘

s= '...abca????'
pat = 'abcabcac'
비교 실패 했을 때?
실패한 지점에서 pat의 맨 앞부분과 같은 곳까지pat을 밀어서 다시 비교 시작

ex)
An engineering enigma is interesting
engineering engine
비교 -> 매치 실패

An engineering enigma is interesting
..........................engineering engine

str 내에 pat과 일치하는 새로운 시작부분까지 밀기

시간 효율 증가