[AL]_학번_이름_보고서.pdf

입력은 문자열이랑 Pattern을 찾을 substring이 주어지며 substring에 대한 문자열 패턴의 개수를 출력하는 문제

String Hashing, Z-Algorithm ,Suffix Array 등을 이용하여 Pattern Matching을 구현하여 문제를 해결할 수 있음.

본 설명은 String Hashing을 통해 문제를 해결하려고 시도하였으나

String의 길이가 일정부분을 넘어가게 되면

TIME LIMIT EXCEEDED Error가 나타나였고 실습 제한시간 안에 끝내지 못했다.

하지만 그외의 Test Case는 모두 통과하였고, 그에 대한 보고서를 작성한다.

1. 우선 DP를 통해 입력으로 들어온 String s의 prefix s[0..k]를 O(n) 시간에 구하고
2. p[k] = $A^k modB$를 Dp로 구하여
3. 임의의 a > 0에 대해 임의의 substring s[a..b]의 hash function값을 길이 O(1)시간에 구하는 함수를 만들었다.
4. 각 s의 위치부터 시작하여 길이가 p인 substring의 hash function 값과
5. pattern p의 hash function의 값이 일치하는 경우에만 두 string을 비교하여
6. 그 두 string의 hash function이 같을 경우 일치한다고 간주하고 같은것의 수를 센다
7. 이때 앞선 preprocessing을 통해 s의 substring의 hash function의 값을 구하고 저장해놓았으므로
8. s의 모든 substring의 hash function 값을 O(1) 시간에 계산이 가능하다.

Hash Function은 특성상 언제나