[Algorithms] KMP 알고리즘

class KMP {
public:
	string str, pat;
	vector<int> table;
	vector<int> ans;
		
	void getTable() {
		table.resize(pat.length());
		int left = 0;
		for (int i = 1; i < pat.length(); i++) {
			while (left > 0 && pat[left] != pat[i]) {
				left = table[left - 1];
			}
			if (pat[left] == pat[i]) {
				table[i] = left + 1;
				left++;
			}
		}
	}

	void getAns() {
		getTable();
		int patIdx = 0;
		for (int strIdx = 0; strIdx < str.length(); strIdx++) {
			while (patIdx > 0 && pat[patIdx] != str[strIdx]) {
				patIdx = table[patIdx - 1];
			}
			if (pat[patIdx] == str[strIdx]) {
				if (patIdx == pat.length() - 1) {
					ans.push_back(strIdx - pat.length() + 1);
					patIdx = table[patIdx];
				}
				else {
					patIdx++;
				}
			}
		}
	}
};

 

 

+ 4/22

시험 준비하면서 코드 봤는데 table을 만들 때

if (pat[left] == pat[i]) {
	table[i] = left + 1;
	left++;
}

이 부분에서 저 조건문이 굳이 필요할까 라는 의문이 들었지만

그 위의 while문을 종료하는 상황은 pat[left] == pat[i]인 경우도 있지만 left == 0이 될 수도 있기 때문에 필요하다.

left == 0이고 pat[0] != pat[i]이면 table[i] = 0이다.

 

또, table[0] = 0이고 for문은 i = 1부터 확인한다는 걸 잊지 말기.

 

그리고

while (left > 0 && pat[left] != pat[i]) {
	left = table[left - 1];
}

pat[left] != pat[i]이면 (0 ~ left - 1까지의 substring에서 접두사 == 접미사인 접두사의 마지막 인덱스) + 1로 이동해야 하는데,

문자열의 마지막 인덱스는 (문자열의 길이 - 1)이고, left는 마지막 인덱스 + 1로 업데이트 해야 하기 때문에

이 차이가 상쇄되어 그냥 (접두사 == 접미사인 접두사의 길이)로 이동하면 된다.

table에 (접두사 == 접미사인 접두사의 길이)가 저장되어 있으므로 left = table[left - 1]이다.