HDU6583 Typewritter（后缀自动机）

给定一个字符串，主角需要用打字机将字符串打出来，每次可以：

（1）花费p来打出任意一个字符。

（2）花费q将已经打出的某一段子串复制到后面去。

求解最小花费。

题解：

考虑dp。

设置dp[i]表示已经打出前i个字符的最小花费，这样设置状态是没有后效性的。

那么显然有：

dp[i]=dp[i-1]+p;

这样就可以将第一种方案的转移算出来。

对于第二种方案，我们可以考虑维护一个j，使得s[j+1~i]可以由s[1~j]中的一部分复制而来。

具体实现利用后缀自动机来维护，当不满足条件（1）时，就不断往后添加字符，并让j=j+1。

当满足条件（1）时，就可以有：

dp[i]=min(dp[i],dp[j]+q);

实现细节：

当找到满足条件的j时，记录在后缀自动机上的最后的匹配位置，每次i或j变化的时候，检查cur的link指针指向位置的终点集合长度是否大于已匹配的长度，如果是，就可以往link指针方向跳，之后继续匹配。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
const int kind=26;
struct node {
    node * next[kind];
    node * link;
    int len;
    node () {
        link=0;
        len=0;
        memset(next,0,sizeof(next));
    }
}Node[maxn*2+100];
int tot;
node * newNode (int len=0) {
    memset(Node[tot].next,0,sizeof(Node[tot].next));
    Node[tot].link=0;
    Node[tot].len=len;
    return &Node[tot++];
}
node * root;
node * last;
void extend (int w) {
    node * p=last;
    node * cur=newNode(p->len+1);
    while (p&&p->next[w]==0) {
        p->next[w]=cur;
        p=p->link;
    }
    if (p) {
        node * q=p->next[w];
        if (p->len+1==q->len)
            cur->link=q;
        else {
            node * clone=newNode(p->len+1);
            memcpy(clone->next,q->next,sizeof(q->next));
            clone->link=q->link;
            q->link=clone;
            cur->link=clone;
            while (p&&p->next[w]==q) {
                p->next[w]=clone;
                p=p->link;
            }
        }
    }
    else
        cur->link=root;
    last=cur;
}
char s[maxn];
ll dp[maxn];
int main () {
    while (~scanf("%s",s+1)) {
        tot=0;
        root=newNode();
        last=root;
        ll p,q;
        scanf("%lld%lld",&p,&q);
        int n=strlen(s+1);
        int j=1;
        dp[1]=p;
        extend(s[1]-'a');
        node * cur=root->next[s[1]-'a'];
        for (int i=2;i<=n;i++) {
            dp[i]=dp[i-1]+p;
            while (1) {
                while (cur!=root&&cur->link->len>=i-j-1) cur=cur->link;
                if (cur->next[s[i]-'a']!=NULL) {
                    cur=cur->next[s[i]-'a'];
                    break;
                }
                else
                    extend(s[++j]-'a');
            }
            dp[i]=min(dp[i],dp[j]+q);
        }
        printf("%lld
",dp[n]);
    }
}