#32484 Headline Heat

뇌풀이인 이유는 시험기간이라 구현을 할 시간이 없기 때문이다...
까먹기전에 여기에 기록한다.

 

 

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

학회에서 예선 대비 팀 연습했을 때 만났던 문제이다. 아호코라식을 몰라서 실제 연습때는 던졌는데 롸선배의 풀이 세션에서 깨달음을 좀 얻어서 작성.

여기서 S=10^6,N=10^5정도로 본다.

 

우선.... 이 문제는 여러 문자열 매칭을 하는 부분을 빼고 풀어보자.

연결되는 부분들에 대해 간선을 이어서 유니온 파인드를 한다고 생각하면 동치임을 쉽게 알 수 있다.

즉 같은 유파의 문자열들은 같은 횟수만큼 나왔어야 한다.

 

따라서 각 유파에 대해서, 가장 등장횟수가 많은 값 x, 등장횟수가 최대인 문자열의 개수 y, 그 유파의 크기 z를 관리하면

항상 x==y이어야 함을 알 수 있는데,

우리는 등장횟수를 incremental 하게 셀 거기 때문에 이 모든 값들을 관리 할 수 있다.

 

디테일은 생략~

 

이제 문자열 매칭을 통한 등장횟수를 세보자.

아마 여기서 아호코라식을 쓰는게 정해일거 같은데...

1. 해싱을 이용한 풀이

매칭해야 하는 문자열들의 서로 다른 길이는 많아야 sqrt(S)정도이다. 이는 서로 다른 길이들의 합을 생각해보면 짧아야 1+2+3....X<=S이어야 하므로 쉽게 알 수 있다.

 

그렇다면 그 서로 다른 길이 들에 대한 문자열들의 해시값을 넣고, map으로 찾아가면서 등장 횟수를 세주면 된다.

rolling hash로 잘 구현해주면 되는데 문제는 S가 꽤 크다.... 사실 sqrt(S)정도라고 했지만 sum(1,n)=n*(n+1)/2이므로 X에 1000을 넣으면 S-sum(1,1000)=5*10^5정도라 계산값이 1000*(5*10^5)번 나오는데 map에 찾는것도 있고, 유파에서 연산도 있어서 시간이 터진다. 

 

int로 해싱하고, 뭐 별별 짓 다했는데 터지는걸 보니 빡센가 보다.

 

그래서 생각한점...-> 길이 종류가 다양하다== 각 길이별 문자열이 많이 없다. == 각 길이별 첫 글자로 나올 수 있는 문자는 제한적이다.  이를 이용하면 상수정도는 나눠질거 같은데...짜보진 않음

 

2. suffix automation을 이용한 풀이

suffix automataion의로 풀면 장점은 노드마다 그 위치에서의 등장 횟수를 세어 줄 수 있다는 점이다.

게다가 노드는 많아야 O(2S)개이다.

 

그럼 우리는 이런 짓거리를 할 수 있는데, 매칭해야 하는 문자열들의 집합을 사전순으로 정리하고, sa를 순회할 것이다.

이때 각 노드별 구간 [L,R]을 정의하는데,이는 문자열 집합의 L번째 문자열 부터 R번째 문자열까지 이 노드에 도달 할 수 있다는 점이다. 이를 잘 전이하면 되는데 결국 우리는 연속된 구간의 합에 더해주는 연산을 최종적으로는 O(2S)번 한다. 게다가 중요한 점은, 이 구간들은 겹치지 않는다. 이를 이용하면 최종 정답을 구할 수 있는데, 꽤 귀찮아질것 같다.