문제

Pn이 다음과 같을때 문자열에 Pn이 몇번 들어가는 갯수를 세는 문제다.

예를 들어
다음과 같은 예제는 4개를 발견할 수 있다.

시간복잡도가 문제

문제는 범위다.

대충 n번씩 검색하며 Pn을 체크하는데 n에 시간이 들어
n^2이 든다.

그래서 먼저 그렇게 코드를 작성했는데 역시나 100만에 n^2는 10^12이므로 10^8이 1초임을 가만하면 너무 오래걸린다.

n번 검사하지말자

최근 이러한 문제를 투포인터로 해결했었다.
left, right를 정해서 굳이 처음부터 검사하는게 아닌
상황에 맞게 left와 right를 옮기면 되는것이다.

Pn이 IOIOIOIOIOIOI라면 IOIOIOIOIOIOIII가 안된다면
굳이 다음 인덱스부터가 아닌 해당 범위를 모두 뛰어넘으면 되었다.

또한 IOIOIOIOIOIOI이 가능하다면 왼쪽에 두개를 빼면 나머지는 가능하게된다.

분류가 투포인터는 아니었지만 나는 투포인터인거 같다.
어렵다.

code

#include <iostream>
#include <string>
using namespace std;

#define MAX int(1e6)
int n, m;
char s[MAX],p[MAX];

bool check(int s_i) {
	if (s_i + 2 * n >= m) return false;
	for (int i=0; i < 2*n+1; i++) {
		if (p[i] != s[s_i + i]) return false;
	}
	return true;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifdef _DEBUG
	freopen("B5525.in", "r", stdin);
#endif
	cin >> n >> m;
	cin >> s;
	// make pn
	for (int i = 0; i < 2 * n + 1; i++) {
		if (i & 1) p[i] = 'O';
		else p[i] = 'I';
	}
#ifdef _DEBUG
	cout << "[p] ";
	for (int i = 0; i < 2 * n + 1; i++) cout << p[i];
	cout << endl;
#endif
	int s_i = 0, cnt = 0, ans = 0;
	while (s_i < m) {
		if (s[s_i] == p[cnt]) {
			cnt++;
		}
		else {
			if (s[s_i] == 'I') cnt = 1;
			else cnt = 0;
		}
		if (cnt == 2 * n + 1) {
			ans++;
			// 왼쪽 2개만 빼줌
			cnt -= 2;
		}
		s_i++;
	}
	cout << ans;
}