kmp(교육용)

KMP(교육용).cpp

#include <cstdio>
#include <string>
#include <vector>
using namespace std;
#define MAX_N 1000001

char t[MAX_N], p[MAX_N];
int n, m;
vector<int> res;
int fail[MAX_N];

void fail_func() {
	for (int i = 1, j = 0; i < m; i++) {
		while (j > 0 && p[i] != p[j]) {
			j = fail [j - 1];
		}
		if (p[i] == p[j]) {
			fail[i] = ++j;
		}
	}
}

void kmp() {
	for (int i = 0, j = 0; i < n; i ++ ) {
		while (j > 0 && t[i] != p[j]) {
			j = fail[j-1];
		}
		if (t[i] == p[j]) {
			if (j == m - 1) {
				res.push_back(i - m + 1);
				j = fail[j];
			}
			else j++;
		}
	}
}

int main()
{
	scanf("%[^\n]", t);
	getchar();
	scanf("%[^\n]", p);

	n = strlen(t);
	m = strlen(p);

	fail_func();
	kmp();

	printf("%d\n", res.size());
 	
  for(int i=0; i<res.size(); i++){
    printf("%d ", res[i]);
  }

	return 0;
}