nefu 1267 挑战字符串(AC自动机+dp)

本文主要是介绍nefu 1267 挑战字符串(AC自动机+dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小华非常喜欢字符串，现在他有n个字符串s[1]~s[n]，他觉得每个字符串都很漂亮，然后就给每个字符串一个美丽值v[1]~v[n]。小华刚刚得到一个新的字符串t，他想定义字符串t的美丽值，定义方法：字符串t的美丽值为字符串t包含的子串（上述n个字符串之一）对应的美丽值之和的最大值（子串之间不能重叠，同一个子串可出现并计算多次，因为不能重叠，所以两个重叠的子串存在取舍，存在不同的值）。小华不太擅长计算，你能帮帮小华计算出字符串t的美丽值吗？

输入包含多组数据。
每组数据第一行一个整数n（1<=n<=1000）。
接下来n行每行一个字符串s[i]和一个整数v[i]（1<=|s[i]|<=1000，1<=v[i]<=1000）。
最后一行一个字符串t(1<=|t|<=1e6)。
所有的字符串均由小写英文字母构成。

输出字符串t的美丽值。

4
abc   2
ab    3
abca  5
adf   8
abcab

6

上述的样例中，字符串abcab包含abc、ab、abca这三个子串，由于子串之间不能重叠计算，所以字符串abcab的美丽值最大为2个ab，对应3+3=6

CJJ

题意：中文题。

思路：用AC自动机存下所有字符串的价值和长度，再进行计算他们的最大价值的时候，有一个类似01背包的状态转移方程

dp[i+1]=max(dp[i+1-tmp->len]+tmp->v,dp[i+1])   //dp[i+1]表示i+1长度的字符串的最大美丽值。

因为在匹配的过程中，可能在一开始就会失配，导致tmp直接等于了root进不来状态转移方程，所以需要在之前就把dp[i]的值赋给dp[i+1]保留状态。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1e6+5;
char str[maxn];
long long dp[maxn];
struct node
{node* next[26];node* fail;int len;int cnt;int v;node(){memset(next,NULL,sizeof(next));fail=NULL;len=0;v=0;}
};
queue<node* >que;
void in(node* root,char str[],int v)
{int i=0;root->len=0;node* now=root;while(str[i]){int x=str[i]-'a';if(now->next[x]==NULL){now->next[x]=new node();}now=now->next[x];i++;}now->v=v;now->len=i;
}
void makefail(node* root)
{que.push(root);while(!que.empty()){node* now=que.front();que.pop();for(int i=0;i<26;i++){if(now->next[i]!=NULL){if(now==root){now->next[i]->fail=root;}else{node* p=now->fail;while(p!=NULL){if(p->next[i]!=NULL){now->next[i]->fail=p->next[i];break;}p=p->fail;}if(p==NULL)now->next[i]->fail=root;}que.push(now->next[i]);}}}
}
long long query(node* root,char str[])
{memset(dp,0,sizeof(dp));int i=0;node* now=root;while(str[i]){dp[i+1]=dp[i];int x=str[i]-'a';while(now->next[x]==NULL&&now!=root) now=now->fail;now=now->next[x];if(now==NULL)now=root;node * tmp=now;while(tmp!=root){if(tmp->v>0){dp[i+1]=max(dp[i+1-tmp->len]+tmp->v,dp[i+1]);}tmp=tmp->fail;}i++;}return dp[i];
}
int main()
{int n,v;while(~scanf("%d",&n)){node* root=new node();for(int i=1;i<=n;i++){scanf("%s%d",str,&v);in(root,str,v);}makefail(root);scanf("%s",str);printf("%lld\n",query(root,str));}return 0;
}

这篇关于nefu 1267 挑战字符串(AC自动机+dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！