HDU 6583 Typewriter(접미사 로봇)

Typewrite

\[ Time Limit: 1500 ms\quad Memory Limit: 262144 kB\]

제목의 뜻

문자열\(s\) 을 주십시오. 이 문자열을 만들어야 합니다. 매번\(q\) 를 써서 끝에 임의의 문자를 추가하거나\(p\) 를 써서 만들어진 하위 문자열을 끝까지 복사할 수 있습니다. 최소한 얼마의 문자열이 필요한지 물어보십시오.

사고의 방향

명령\(dp[i]\)는 제\(i\) 비트로 구성하는 데 필요한 최소 비용을 나타냅니다.첫 번째는\(q\)를 직접 써서 끝에 추가하고\(dp[r]=dp[r-1]+q\) 두 번째는\(p\)를 써서 일부분을 끝까지 복사하고\(s[l+1...r]\)를 설정하면 복사된 문자열이므로\(s[l+1...r]\ins[1.l]\)를 만족시켜야 한다.\(dp[r]=dp[l]+p\)는 문제는\(l\)를 어떻게 유지하는가이다.접미사 자동기를 이용하면 모든 하위 문자열의 성질을 나타낼 수 있고\(pos\)는 조건을 충족시키는\(s[l+1...r]\)가 접미사 자동기에 있는 노드의 위치를 나타낼 수 있다.\(s[r]\)를 삽입할 때마다\(s[l+1...r-1]\ins[1...l]\impliess[l+1...r]\ins[1...l]\)에서\(pos\) 노드를\(s[r]\) 방향으로 이동시켜야 합니다.이동할 수 있다면\(pos\)를 직접 이동하십시오. 그렇지 않으면 이 자동기를 확장해서\(s[l]\)를 삽입한 후에 이동할 수 있는지 시도합니다.이 과정에서 조건 범위를 충족시키는 노드에\(pos\)를 계속 유지합니다.

문제는\(pos\)가\(s[r]\) 방향으로 언제 이동할 수 없느냐는 것이다. 이 경우\(pos\) 노드에\(s[r]\)가 존재하지 않는다는 것이다.

문제는\(pos\)가 조건에 부합되는 범위 내에서 어떻게 유지되는지 하는 것이다.\(pos\) 노드는 같은 성질의 길이를 포함하고 있음을 알고 있다.\(len[fa[pos]+1\)에서\(len[pos]\)까지의 하위 문자열을 포함하고 있다. 우리는 이 안에 가장 짧은 하위 문자열을 보장하기만 하면 된다. (len[fa[pos]+1\) 너무 길지 않고 뒷부분의 문자열을 표시할 수 있어야 한다.\(s[r]\)를 삽입하기 전에는\(r-1\)만 도착하고\(len[fa[pos]+1\leq(r-1)-(l+1)+1\),\(s[r]\)를 삽입한 후에는\(r\),\(len[fa[pos]]]+1\leqr-(l+1)+1\)

#include 

전재 대상:https://www.cnblogs.com/Jiaaaaaaaqi/p/11253183.html