문제

부분 문자열

풀이

시간복잡도 O(n)이 나오면서 indexof, contains, matches 와 같이 해결하려면 KMP 알고리즘을 사용해야 한다. 실제로 알고리즘 분류도 구현, 문자열이라서 contains로 해도 될거같은데... 실제로 contains 같은 java api 는 KMP알고리즘을 사용하지 않는다. 이 java api들이 kmp알고리즘을 채택하지 않는 이유는 공간복잡도 때문이라고 한다

1. 인덱스 부터 일치되는 문자가 나오는 개수를 저장한다

		int j = 0;
        int[] pi = new int[p.length()];
        for (int i = 1; i < p.length(); i++) {
            while (j > 0 && p.charAt(i) != p.charAt(j)) {
                j = pi[j - 1];
            }
            if (p.charAt(i) == p.charAt(j)) {
                pi[i] = j += 1;
            }
        }

2. 2개의 문자열이 일치하는 개수가 같으면 1을 출력하고 만약 문자열을 전부 돌때 비교군의 문자열의 개수와 같지 않고 같은 문자열이 존재 하지 않으면 0이 출력된다

		j = 0;
        for (int i = 0; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != p.charAt(j)) {
                j = pi[j - 1];
            }
            if (s.charAt(i) == p.charAt(j)) {
                if (j == p.length() - 1) {
                    System.out.println(1);
                    System.exit(0);
                } else {
                    j++;
                }
            }
        }
        System.out.println(0);

전체 코드

전체 코드