U E D R , A S I H C RSS

Data Structure/String

๊ฐ€์žฅ ๊ธฐ๋ณธ์ ์ธ ํŒจํ„ด ๋งค์นญ ์•Œ๊ณ ๋ฆฌ์ฆ˜

~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 -- ํ™ฉ์žฌ์„ 
        ๊ณ ๋งˆ์›Œ.^^๊ทผ๋ฐ C๋กœ fail() ๊ตฌํ˜„ ๋ถ€๋ถ„์€ ๋” ์‹ ๊ธฐํ•˜๋‹ค. ใ…กใ…ก; --Leonardong


Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:05
Processing time 0.0046 sec