Text Search


텍스트 t 안에서 패턴 p의 존재를 찾는 것

i는 텍스트 t의 인덱스, 패턴 p를 찾으면 t안에서 그 패턴이 시작되는 i를 리턴

패턴이 없을 경우 0를 리턴


Input : p(indexed from 1to m), m, t(indexed from 1to n), n

Output : i


text_search(p, m, t, n){

          for i=1 to n-m+1{

               j=1

               //j는 패턴 p의 인덱스


               //while문은 t<SUB>i </SUB>… t<SUB>i+m-1</SUB> 과 p<SUB>1</SUB> … p<SUB>m</SUB>을 비교한다

               while(t<SUB>i+j-1</SUB> == p<SUB>j</SUB>){

                      j=j+1

                      if(j>m)

                         return I

                 }

             }

             return 0

}




이산수학 알고리즘의 시간적 복잡도야

이거 교수님이 답이 mn이라는데
도저히 이해가 안돼

우리 빅오 같은것도 자세히 안배웠고
교수님이 답을 O(mn)이라 한 것도 아니고 mn 이라 하셨어
베스트 워스트 캐이스 이런 말도 안하고 그냥 mn.


어떤식으로 해서 mn이 나온거야?ㅠ

책이 원서라 사전 펴들고 읽다가 읽다가 결국 이해 못해서 올려봐
도움 좀 줘 횽들ㅠ

<sub>요건 아래 첨자야ㅠ