acmicpc.net 5582(Suffix Automaton), 9249, 9253(Suffix Automaton)

https://www.acmicpc.net/problem/5582

Suffix Automaton 문제.

#include <cstdio>
#include <cstring>
using namespace std;
#define max(a,b) (a>b?a:b)
const int MN = 270500;
const int maxState = (MN << 1);
struct State {
	State *go[26], *suffix;
	int depth, id;
	long long cnt;
};
State pool[maxState], *point, *root, *sink;
int size;
State *newState(int dep) {
	point->id = size++;
	point->depth = dep;
	return point++;
}
void init() {
	point = pool;
	size = 0;
	root = sink = newState(0);
}
void insert(int a) {
	State *p = newState(sink->depth+1);
	State *cur = sink, *sufState;
	while (cur && !cur->go[a]) {
		cur->go[a] = p;
		cur = cur->suffix;
	}
	if (!cur)
		sufState = root;
	else {
		State *q = cur->go[a];
		if (q->depth == cur->depth + 1)
			sufState = q;
		else {
			State *r = newState(cur->depth+1);
			memcpy(r->go, q->go, sizeof(q->go));
			r->suffix = q->suffix;
			q->suffix = r;
			sufState = r;
			while (cur && cur->go[a] == q) {
				cur->go[a] = r;
				cur = cur->suffix;
			}
		}
	}
	p->suffix = sufState;
	sink = p;
}
void solve(char buf[]) {
	int len = strlen(buf);
	int tmp = 0, ans = 0, anspos = 0;
	State *cur = root;
	for (int i = 0; i < len; i++) {
		if (cur->go[buf[i]-'A']) {
			tmp++;
			cur = cur->go[buf[i]-'A'];
		} else {
			while (cur && !cur->go[buf[i]-'A'])
				cur = cur->suffix;
			if (!cur) {
				cur = root;
				tmp = 0;
			} else {
				tmp = cur->depth + 1;
				cur = cur->go[buf[i]-'A'];
			}
		}
		if (ans < tmp) ans = tmp, anspos = i-tmp+1;
	}
	printf("%d\n",ans);
	//for (int i = anspos; i <= anspos+ans-1; i++) printf("%c",buf[i]);
}
char ch[MN];
int main() {
	scanf("%s", ch);
	init();
	int len = strlen(ch);
	for (int i = 0; i < len; i++) 
		insert(ch[i]-'A');
	scanf("%s", ch);
	solve(ch);
	return 0;
}

https://www.acmicpc.net/problem/9249

위의 소스에서 main과 solve부분의 -'A'부분을 'a'로 바꿔주고, solve함수의 주석처리된 for문을 풀어준다.

https://www.acmicpc.net/problem/9253

solve 함수부분부터 바꿨다. 그부분만 올림.

char answer[MN];
bool solve(char buf[]) {
	int len = strlen(buf);
	int tmp = 0, ans = 0, anspos = 0;
	State *cur = root;
	for (int i = 0; i < len; i++) {
		if (cur->go[buf[i]-'a']) {
			tmp++;
			cur = cur->go[buf[i]-'a'];
		} else {
			while (cur && !cur->go[buf[i]-'a'])
				cur = cur->suffix;
			if (!cur) {
				cur = root;
				tmp = 0;
			} else {
				tmp = cur->depth + 1;
				cur = cur->go[buf[i]-'a'];
			}
		}
		if (ans < tmp) ans = tmp, anspos = i-tmp+1;
	}
	//printf("%d\n",ans);
	bool flag = true;
	for (int i = anspos,j=0; i <= anspos+ans-1; i++,j++) 
		if(buf[i]!=answer[j])
			flag=false;
	return flag;
}
char ch[MN];
int main() {
	scanf("%s", ch);
	init();
	int len = strlen(ch);
	for (int i = 0; i < len; i++) 
		insert(ch[i]-'a');
	scanf("%s", ch);
	scanf("%s", answer);
	if(solve(ch))
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}