KMP알고리즘에서 prefix와 suffix를 비교하는 fail함수를 만드는 과정에서 구할 수 있다.
단 이때 이 문제에서 나올 수 있는 모든 prefix의 경우를 살펴야하기 때문에
for문을 한번 돌면서 시작지점을 정하고 그때마다 kmp fail함수를 만들어서
가장 길게 매칭되는 prefix suffix의 길이를 구해야 한다.
2. 문제풀이코드
#include <iostream>
using namespace std;
int fail[5003];
int getFail(const string &s, int start) {
int ans = 0;
for(int i=0; i <5003; i++){
fail[i] = 0;
}
int j = 0;
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s[i] != s[j]) {
j = fail[j - 1];
}
if (s[i] == s[j]) {
fail[i] = ++j;
ans = max(ans, j);
}
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
int ans = 0;
for (int i = 0; i < s.length(); i++) {
ans = max(ans, getFail(s.substr(i,s.length()-i), i));
}
cout << ans << '\n';
}
system V 계열의 경우 시그널 핸들러를 한번 사용 하면 시그널 처리 방법을 기본 처리 방법(SIG_DFL)로 재설정한다.
시그널이 들어올 때마다 시그널 핸들러를 호출하려면 매번 시그널 핸들러를 재지정해야한다.
BSD 계열의 경우는 기본 처리 방법(SIG_DFL)로 재설정 하지 않고 계속 시그널 핸들러를 계속 사용하고,
리눅스 계열의 경우 커널의 signal(2) 시스템 콜은 시스템 V와 같은 방식으로 동작하고,
gcc의 glibc 2부터 signal(3) 함수는 signal(2)를 호출하지 않고 sigaction(2)를 호출해 BSD 형식으로 동작한다.
시그널 집합
시그널을 개별적으로 처리하지 않고 복수의 시그널을 처리하기 위해 도입한 개념이다.
POSIX에서 도입했다.
시그널 집합의 처리를 위한 구조체 sigset_t
typedef struct{
unsigned int __sigbits[4];
} sigset_t;
시그널을 비트 마스크(128bit)로 표현한다. 각 비트가 특정 시그널과 1:1로 연결된다.
비트 값이 1이면 해당 시그널이 설정된 것이고, 0이면 시그널 설정이 안된 것이다.
시그널 처리 함수
//sigemptyset(3)을 활용하여 시그널 집합에서 모든 시그널을 0으로 설정할 수 있다.
int sigemptyset(sigset_t *set);
//시그널 집합에서 모든 시그널을 1로 설정
int sigfillset(sigset_t *set);
//시그널 집합에 시그널 설정 추가
int sigaddset(sigset_t *set, int signo);
//시그널 집합에 시그널 설정 삭제
int sigdelset(sigset_t *set, int signo);
//시그널 집합에서 시그널이 포함되어 있는지 확인
int sigismember(sigset_t *set, int signo);
#include <unistd.h>
#include <signal.h>
#include <stdlib.h>
#include <stdio.h>
int main() {
sigset_t st;
sigemptyset(&st);
sigaddset(&st, SIGINT);
sigaddset(&st, SIGQUIT);
if(sigismember(&st, SIGINT))
printf("SIGINT is setting.\n");
//__val은 시스템 환경마다 다른 변수 이름을 사용해야한다 ubuntu에서는 __val 사용
printf("** Bit Pattern: %x\n", st.__val[0]);
return 0;
}
#include <unistd.h>
#include <signal.h>
#include <stdlib.h>
#include <stdio.h>
static void sig_fpe(int);
int main() {
pid_t pid;
int i;
signal(SIGFPE, sig_fpe);
i = i/0;
}
static void sig_fpe(int signo){
pid_t pid; int status;
printf("Divide by 0 Error\n");
exit(1);
}
기타 시그널 처리 함수
// 시그널 정보 출력
// s에 지정한 문자열을 붙여 정보 출력
void psignal(int sig, const char *s);
//인자로 받은 시그널을 가리키는 이름을 문자열로 리턴
char *strsignal(int sig);
//시그널 블록킹과 해제
//인자로 받은 시그널을 시그널 마스크에 추가하거나 해제한다
int sighold(int sig);
int sigrelse(int sig);
#include <unistd.h>
#include <signal.h>
#include <stdlib.h>
#include <stdio.h>
void handler(int signo){
char *s;
s = strsignal(signo);
printf(stdout, "Received Signal : %s\n", s);
}
int main() {
if (sigset(SIGINT, handler) == SIG_ERR){
perror("sigset");
exit(1);
}
sighold(SIGINT);
pause();
return 0;
}
이 경우 CTRL+C로 SIGINT를 보내도 프로그램이 종료되지 않는다.
//시그널 집합 블록과 해제
int sigprocmask(int how, const sigset_t *restrict set, sigset_t *restrict oset);
how : 시그널을 블록할 것인지, 해제할 것인지 여부 결정
SIG_BLOCK : set에 지정한 시그널 집합을 시그널 마스크에 추가
SIG_UNBLOCK : set에 지정한 시그널 집합을 시그널 마스크에서 제거
SIG_SETMASK : set에 지정한 시그널 집합으로 현재 시그널 마스크를 대체
set은 블록하거나 해제할 시그널 집합 주소를 의미하고, oset은 NULL 또는 이전 설정값을 저장한 시그널 집합 주소이다.
