본문 바로가기 메뉴 바로가기

ACM-ICPC 상 탈 사람

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

ACM-ICPC 상 탈 사람

검색하기 폼
  • 분류 전체보기 (360)
    • 서버 관련 (9)
      • JS (5)
      • AmazonWebService (1)
      • Backend 지식 (3)
    • 일상 (13)
      • Daliy (1)
      • 잡담 (10)
      • 개인 (2)
    • 알고리즘 관련 (337)
      • BOJ (303)
      • UVaOJ (8)
      • SPOJ (1)
      • 알고리즘&이론 (25)
  • 방명록

LCP array (5)
BOJ)13576 Prefix와 Suffix

문제: icpc.me/13576 prefix와 suffix가 같은 모든 부분문자열은 pi배열을 이용하여 전부 구해줄 수 있다. length -> pi[length] -> pi[[pi[length]]] ... 이런식으로 하지만 이때 부분 문자열의 등장횟수도 구해줘야 한다. suffix의 부분 문자열 등장횟수는 LCP를 이용하여 O(N)에 처리해줄 수 있다. 현재 확인중인 i번째 suffix의 등장횟수는 LCP[i+1]~ LCP[max] 중에서 연속으로 부분 문자열 i의 길이보다 큰 LCP의 개수로 처리해줄 수 있다. 아래 코드에서 dp배열에 suffix의 등장횟수가 담긴다. 12345678910111213141516171819202122232425262728293031323334353637383940414..

알고리즘 관련/BOJ 2017. 3. 13. 02:47
BOJ)11479 서로 다른 부분 문자열의 개수2

문제:icpc.me/11479 서로 다른 부분 문자열의 개수를 세는 문제이다. Suffix Array를 이용하여 LCP Array를 구해준 뒤 0~n 에 대하여 n-SA[i]-LCP[i](해당 Suffix의 길이-LCP) 의 합을 구해주면 된다. 해당 Suffix의 부분 문자열의 경우의 수는 해당 Suffix의 길이지만 이때 LCP만큼 중복되기 때문이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include typedef long long ll;#define MAX_N 1000010using namespace std;char..

알고리즘 관련/BOJ 2017. 2. 8. 01:40
BOJ)9249 최장 공통 부분 문자열

문제: icpc.me/9249 http://jason9319.tistory.com/143와 유사한 문제이다. 두 문자열 사이에 더미를 끼운 뒤 하나로 연결한 후 LCP Array의 최댓값을 구하는데 이때 해당 LCP[i]를 구성하는 SA[i]와 SA[i-1]이 서로 다른 문자열에서 파생된 문자여야 한다. 거기에 해당 부분 문자열을 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #define MAX_N 200020using namespace std;char str[2..

알고리즘 관련/BOJ 2017. 2. 8. 01:36
BOJ)5582 공통 부분 문자열

문제: icpc.me/5582 두 문자열이 주어질 때 공통 부분 문자열의 최대 길이를 출력하는 문제이다. 두 문자열 사이에 나올 수 없는 한 문자열을 더미로 끼운 뒤 두 문자열을 연결하여 (ex ABC!BCD) Suffix Array를 이용하여 LCP Array를 구할 때 비교 되는 접미사 SA[i]와 SA[i-1]가 서로 다른 문자열로부터 파생된 것들 중 LCP의 최대길이를 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #define MAX_N 10000using namespace st..

알고리즘 관련/BOJ 2017. 2. 8. 01:32
BOJ)1605 반복 부분문자열

문제: icpc.me/1605 한 문자열의 부분문자열 중에서 두번 이상 나타나는 문자열 중에 가장 긴 문자열의 길이를 출력하는 문제이다. Suffix Array를 이용하여 LCP Array를 구해준 뒤 LCP Array중 최댓값이 두번 이상 나타나는 문자열 중 가장 긴 문자열이다. 한 부분 문자열이 두번 이상 출현한다면 이를 접두사를 갖는 접미사들은 접미사 배열상에서 항상 인접해 있기 때문이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include #define MAX_N 200020using namespace std;char ..

알고리즘 관련/BOJ 2017. 2. 8. 01:27
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Node.js로 DynamoDB 시작⋯
  • Node.js로 DynamoDB 시작⋯
  • Express와 Apollo server⋯
  • GraphQL 스키마 작성하기⋯
최근에 달린 댓글
  • 도움이 많이 되었습니다 굳굳⋯
  • 간선의 방향을 다 거꾸로 받⋯
  • 넵 요즘은 거의 node js 만⋯
  • 문제 설명 감샇바니다. :) 'B⋯
Total
315,368
Today
35
Yesterday
199
링크
  • 민호형
  • 제주시민
  • 꼴뚜기
  • 김흿
  • 태양쓰
  • 정률이
  • 정이 형
  • stack님
  • 세지니
  • 매브레이커
  • 박트리님
  • 플즈런님
  • 맹킹
  • 송이 블로그
TAG
  • MCMF
  • 트리
  • 이분 매칭
  • MST
  • dfs
  • 그리디 알고리즘
  • 수학
  • disjoint-set
  • BFS
  • 다이나믹 프로그래밍
  • KMP
  • 힙
  • 디닉
  • 좌표 압축
  • SCC
  • 이분 탐색
  • LCP array
  • 네트워크 플로우
  • 위상 정렬
  • 세그먼트 트리
  • lazy propagation
  • 다익스트라
  • partial sum
  • lca
  • 분할 정복
  • 플로이드 워셜
  • 라인 스위핑
  • 에라토스테네스의 체
  • Suffix Array
  • brute force
more
«   2021/03   »
일 월 화 수 목 금 토
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
글 보관함
  • 2020/05 (2)
  • 2020/04 (6)
  • 2020/03 (1)
  • 2018/07 (4)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바