๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ธ ํจํด ๋งค์นญ ์๊ณ ๋ฆฌ์ฆ ¶
~cpp 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; // ์์ฑ ๋์ง ์์์떄 } }
- ์๊ฑด ๊ฑ ์ฌ์ฌํด์ ๋ง๋ค์ด ๋ดค์ต๋๋ค. ๋ญ๊ฐ ์ฝ๋๊ฐ ์ข ๋๋ฌ์ด๊ฑฐ ๊ฐ๊ธด ํ์ง๋ง..-.-;; ์์ผ๋ก ๊ณต๋ถ๋ฅผ ๊ฐ๋
์ ์ตํ๋ฉด ์์ค๋ฅผ ๋ณด๊ธฐ ์ ์ ์ ์์ผ๋ก ๋ง๋ค์ด๋ณด๋ ์ฐ์ต์ ํ๋ ค๊ณ ํฉ๋๋ค.
- Time Complexity๋ O(mn) ์
๋๋ค.(m=๋ฌธ์์ด์ ๊ธธ์ด, n=ํจํด์ ๊ธธ์ด)
- ์ด๊ฒ๋ณด๋ค ๋ ๋ณ์ ๋ฐฉ๋ฒ์ผ๋ก Failure Function์ ์ฐ๋ ๋ฐฉ๋ฒ์ด ์์ ธ.(O(m+n))
- ์๊ฒ์ ๋ฐ์..^^;
- Failure Function ์ค๋ช
์ข ํด์ฃผ์ค ๋ถ? ๋์ฒด ์จ ๋์ ๊ฒ์ ๋ณด์๋ ๊ฐ๋
์ด ์กํ์ง ์๋๊ตฐ์. f(j)๊ฐ์ด ์ด๋ค ๊ณผ์ ์ ๊ฑฐ์ณ์ ๋์ค๋๊ฑด๊ฐ์? -Leonardong
- Failure Function
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 ์ฌ๊ธฐ์ abcabc์ด๋ฏ๋ก i = 2์ด๊ณ i < j์ด๋ฏ๋ก f(5) = 2
j = 4 ์ผ๋, pattern = abcab ์ฌ๊ธฐ์ abcab์ด๋ฏ๋ก i = 1์ด๊ณ i < j ์ด๋ฏ๋ก f(4) = 1
j = 3 ์ผ๋, pattern = abca ์ฌ๊ธฐ์ abca์ด๋ฏ๋ก i = 0์ด๊ณ i < j ์ด๋ฏ๋ก f(3) = 0
๊ฐ์ ๊ฒ์ด ์๋ ๊ฒฝ์ฐ - abcabcac f(j) = -1 -- ํฉ์ฌ์
- Failure Function
- Failure Function ์ค๋ช
์ข ํด์ฃผ์ค ๋ถ? ๋์ฒด ์จ ๋์ ๊ฒ์ ๋ณด์๋ ๊ฐ๋
์ด ์กํ์ง ์๋๊ตฐ์. f(j)๊ฐ์ด ์ด๋ค ๊ณผ์ ์ ๊ฑฐ์ณ์ ๋์ค๋๊ฑด๊ฐ์? -Leonardong