B. 分词

 

有一句句子因为粘贴的时候出现了一点问题空格全部丢失了。现在给一本字典，每个词都对应这个词出现的频率（每十亿）。根据这个频率，我们可以根据下面的公式算出这个词带来的收益 P(word)：

 

P(word)=len2(word)⋅ln(frequency(word))

 

其中 frequency 就是上面所提到的频率。len 指的是单词的长度。

特别的，对于字典中没有出现过的词，P(word)=0。

请对句子进行适当的分割，使得分割得到的所有词收益之和最大。同一个词可以重复出现，收益算作多次。

Input

先给出一本词典，词典的第一行是词条数（词条数约为 40 000），下面每行分别是单词和对应出现频率，用空格隔开。单词中只会出现英文字母大小写，不会有多余的空格。每个单词只会出现一次。频率是一个正实数。

所有单词长度之和不超过 3⋅105，最长单词长度不超过 30。

接下来一行一个整数 T (T≤10)，表示有 T 个查询。

下面 T 行，每行一个句子，句子长度不超过 5 000。句子中保证只含有英文字母大小写。注意单词匹配时，不区分大小写。

词典数据来源于 （可能需要代理），其中  词汇。

查询数据来源于 IELTS Test。

Output

对于每组数据，输出两行。

第一行是一个实数，表示最大能达到的收益。输出和答案相差不超过 10−3 即可认为正确。

第二行输出一连串单词，单词和单词之间用空格隔开。满足：

• 把这些单词依次串联起来可以得到原句子；
• 所有单词的收益值相加得到第一行的实数。

Examples

input

5ano 10ther 30another 10an 300other 201another

output

112.826670another

input

5ano 10.0ther 30.0another 10.0an 300.0other 2000.01another

output

212.837691an other

Note

样例给出的词典与测试数据有所不同。

 

题解：

　　将字典建立AC自动机

　　设定dp[i]表示前i个字母划分可以得到的最大价值

　　那么它可以转移的地方就是 i - 当前的失配指针指向的trie树上的节点所表示的母串长度

　　直接暴力转移就行了。

　　同时用pre记录当前最优是从哪个决策点转过来的

#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair
       
        #define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double Pi = acos(-1.0);const int N = 5e5+10, M = 1e3+20, mod = 1e9+7,inf = 2e5;double sum[N];int len[N],nex[N][27],cnt,head,tail,fail[N],q[N];int ID(char ch) {    if(ch >= 'A' && ch <= 'Z') return ch - 'A';    else return ch - 'a';}void insert(char *s,double x) {    int now = 1, le = strlen(s);    for(int i = 0; i < le; ++i) {        int index = ID(s[i]);        if(!nex[now][index])            nex[now][index] = ++cnt;        len[nex[now][index]] = len[now]+1;        now = nex[now][index];    }    sum[now] = max(sum[now],x);}void build_fail() {    head = 0, tail = 0;    for(int i = 0; i < 26; ++i) nex[0][i] = 1;    fail[1] = 0;    q[tail++] = 1;    while(head != tail) {        int now = q[head++];        for(int i = 0; i < 26; ++i) {            int p = fail[now];            if(!nex[now][i]) {                nex[now][i] = nex[p][i];continue;            }            fail[nex[now][i]] = nex[p][i];            q[tail++] = nex[now][i];        }    }}double x,dp[N];char s[N];int Q,T,pre[N],v[N];int main() {    scanf("%d",&T);    cnt = 1;    for(int i = 1; i <= T; ++i) {        scanf("%s%lf",s,&x);        insert(s,x);    }    build_fail();    scanf("%d",&Q);    while(Q--) {        scanf("%s",s+1);        int n = strlen(s+1);        dp[0] = 0;        int now = 1;        memset(v,0,sizeof(v));        memset(pre,0,sizeof(pre));        for(int i = 1; i <= n; ++i) {            int id = ID(s[i]);            now = nex[now][id];            int tmp = now;            while(tmp > 1) {                if(sum[tmp] != 0) {                    int t = tmp;                    double ns = dp[i - len[t]] + len[t]*len[t]*log(sum[t]);                    if(ns - dp[i] > 0.00001) {                        dp[i] = ns;                        pre[i] = i - len[t];                    }                    tmp = fail[tmp];                }                else {                    tmp = fail[tmp];                }            }            if(dp[i-1] > dp[i]) {                pre[i] = i-1;                dp[i] = dp[i-1];            }        }        int tmp = n;        while(pre[tmp]) {            v[pre[tmp]] = 1;            tmp = pre[tmp];        }        printf("%.10f\n",dp[n]);        for(int i = 1; i <= n; ++i) {            printf("%c",s[i]);            if(v[i]) printf(" ");        }        printf("\n");    }    return 0;}