DataStructure/String - Revision history

Maintenance script: Repair batch-0001 pages from live compare

2026-03-26T23:56:06Z

Repair batch-0001 pages from live compare

← Older revision		Revision as of 23:56, 26 March 2026
Line 10:		Line 10:
	while(1)		while(1)
	{		{
	if(strstr[str_count]==ptnptn[ptn_count]) // 문자 비교해서 같을때		if(strstr[str_count]==ptnptn[ptn_count]) // 문자 비교해서 같을때
	{		{
	ptn_count++; // 패턴과 스트링을 가르키는 걸 한개 증가		ptn_count++; // 패턴과 스트링을 가르키는 걸 한개 증가
Line 79:		Line 79:
	f(j) = -1(Otherwise)		f(j) = -1(Otherwise)

	j = 5 일때, pattern = abcabc 여기서 ~~[[HTML(<~~b~~><~~font color=red~~>)]]~~abc~~[[HTML(<~~/font~~><~~/b~~>)]][[HTML(<~~b~~><~~font color=blue~~>)]]~~abc~~[[HTML(<~~/font~~><~~/b~~>)]]~~이므로 i = 2이고 i < j이므로 f(5) = 2		j = 5 일때, pattern = abcabc 여기서 <b><font color=red>abc</font></b><b><font color=blue>abc</font></b>이므로 i = 2이고 i < j이므로 f(5) = 2

	j = 4 일때, pattern = abcab 여기서 ~~[[HTML(<~~b~~><~~font color=red~~>)]]~~ab~~[[HTML(<~~/font~~><~~/b~~>)]]~~c~~[[HTML(<~~b~~><~~font color=blue~~>)]]~~ab~~[[HTML(<~~/font~~><~~/b~~>)]]~~이므로 i = 1이고 i < j 이므로 f(4) = 1		j = 4 일때, pattern = abcab 여기서 <b><font color=red>ab</font></b>c<b><font color=blue>ab</font></b>이므로 i = 1이고 i < j 이므로 f(4) = 1

	j = 3 일때, pattern = abca 여기서 ~~[[HTML(<~~b~~><~~font color=red~~>)]]~~a~~[[HTML(<~~/font~~><~~/b~~>)]]~~bc~~[[HTML(<~~b~~><~~font color=blue~~>)]]~~a~~[[HTML(<~~/font~~><~~/b~~>)]]~~이므로 i = 0이고 i < j 이므로 f(3) = 0		j = 3 일때, pattern = abca 여기서 <b><font color=red>a</font></b>bc<b><font color=blue>a</font></b>이므로 i = 0이고 i < j 이므로 f(3) = 0

	같은 것이 없는 경우 - abcabcac f(j) = -1 -- [[황재선]]		같은 것이 없는 경우 - abcabcac f(j) = -1 -- [[황재선]]

Maintenance script: Repair MoniWiki formatting after migration

2026-03-26T14:01:36Z

Repair MoniWiki formatting after migration

← Older revision		Revision as of 14:01, 26 March 2026
Line 36:		Line 36:
	** Failure Function 설명 좀 해주실 분? 대체 써 놓은 것을 보아도 개념이 잡히질 않는군요. f(j)값이 어떤 과정을 거쳐서 나오는건가요? -[[Leonardong]]		** Failure Function 설명 좀 해주실 분? 대체 써 놓은 것을 보아도 개념이 잡히질 않는군요. f(j)값이 어떤 과정을 거쳐서 나오는건가요? -[[Leonardong]]
	** Failure Function		** Failure Function
	{\| class="wikitable"		{\| class="wikitable" style="width:100%;"
	\|-		\|-
	\| j		\| j
Line 90:		Line 90:
	----		----
	DataStructure		DataStructure

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:05Z

New page

= 가장 기본적인 패턴 매칭 알고리즘 =
int nfind(char *strstr,char *ptnptn)
{
int str_len=strlen(str); // 문자열의 길이
int ptn_len=strlen(ptn); // 패턴의 길이

int str_count=0; // 카운터
int ptn_count=0;

while(1)
{
if(strstr[str_count]==ptnptn[ptn_count]) // 문자 비교해서 같을때
{
ptn_count++; // 패턴과 스트링을 가르키는 걸 한개 증가
str_count++;
}
else
{
if(ptn_count==0)
str_count++;
ptn_count=0; // 다를때는 패턴은 0으로
}

if(ptn_count==ptn_len) // 패턴이 문자열 내에 있을때 그 시작 위치 리턴
return str_count-ptn_len+1;

else if(str_count==str_len) // 패턴이 문자열 내에 없을때 거짓(다 돌았는데 카운트가
return -1; // 완성 되지 않았을&#46468;
}
}

* 요건 걍 심심해서 만들어 봤습니다. 뭔가 코드가 좀 더러운거 같긴 하지만..-.-;; 앞으로 공부를 개념을 익히면 소스를 보기 전에 제 손으로 만들어보는 연습을 하려고 합니다.
* Time Complexity는 O(mn) 입니다.(m=문자열의 길이, n=패턴의 길이)
* 이것보다 더 낳은 방법으로 Failure Function을 쓰는 방법이 있져.(O(m+n))
* 요것은 밑에..^^;
** Failure Function 설명 좀 해주실 분? 대체 써 놓은 것을 보아도 개념이 잡히질 않는군요. f(j)값이 어떤 과정을 거쳐서 나오는건가요? -[[Leonardong]]
** Failure Function
{| class="wikitable"
|-
| j
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
|-
| pattern
| a
| b
| c
| a
| b
| c
| a
| c
| a
| b
|-
| f(j)
| -1
| -1
| -1
| 0
| 1
| 2
| 3
| -1
| 0
| 1
|}

f(j) = largest i such that i < j and 문자열의 0 ~ i번째 = 문자열의 (j - i) ~ j번째, if such an i exists

f(j) = -1(Otherwise)

j = 5 일때, pattern = abcabc 여기서 [[HTML()]]abc[[HTML()]][[HTML()]]abc[[HTML()]]이므로 i = 2이고 i < j이므로 f(5) = 2

j = 4 일때, pattern = abcab 여기서 [[HTML()]]ab[[HTML()]]c[[HTML()]]ab[[HTML()]]이므로 i = 1이고 i < j 이므로 f(4) = 1

j = 3 일때, pattern = abca 여기서 [[HTML()]]a[[HTML()]]bc[[HTML()]]a[[HTML()]]이므로 i = 0이고 i < j 이므로 f(3) = 0

같은 것이 없는 경우 - abcabcac f(j) = -1 -- [[황재선]]
고마워.^^근데 C로 fail() 구현 부분은 더 신기하다. ㅡㅡ; --[[Leonardong]]

----
DataStructure