[정올 1332] 작명하기

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&code=1332&sca=99 

JUNGOL

#include <stdio.h>

const int LM = 400100;
char str[LM];
int len, fail[LM], ans[LM], alen; //0에서 idx까지의 접두사=접미사인 최대 길이

int strlen(char* s, int len = 0) {
	while (s[len]) len++;
	return len;
}
void preKMP() { //fail 배열 채우기
	for (int i = 2, prelen = 0; i <= len; i++) { //2번째 문자열부터 끝까지 찾는다.
		while (prelen && str[prelen + 1] != str[i]) prelen = fail[prelen]; //현재 누적된 접두접미사가 안 되면 하나 내려가서 비교
		if (str[prelen + 1] == str[i]) fail[i] = ++prelen;
	}
}

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%s", str + 1);
	len = strlen(str + 1);
	preKMP();
	ans[alen++] = len;
	for (int i = len; fail[i] != 0; i = fail[i]) {
		ans[alen++] = fail[i];
	}
	for (int i = alen - 1; i >= 0; i--) printf("%d ", ans[i]);
	printf("\n");

	return 0;
}