hdoj2296(待完成)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;
#define maxn 120
#define CH 27
int chd[maxn][CH];
int fail[maxn],val[maxn];
int sz;
char id[27];
void init(){
    memset(chd[0],0,sizeof(chd[0]));
    sz=1;
    val[0]=0;
}
void insert(char s[],int type,int v[]){
    int i=0,p=0;
	int len=strlen(s);
    for(i=0;i<=len-1;i++)
	{
        int x=s[i]-'a'+1;
        if(!chd[p][x]){
            memset(chd[sz],0,sizeof(chd[sz]));
            val[sz]=0;
            chd[p][x]=sz++;
        }
        p=chd[p][x];
    }
    val[p]=v[type];
}
void build_fail(){
    queue<int> que;
    for(int i=1;i<=CH-1;i++)
		if(chd[0][i])
		{
			fail[chd[0][i]]=0;
			que.push(chd[0][i]);
		}
    while(!que.empty())
	{
        int p=que.front();
        que.pop();
        for(int i=1;i<=CH-1;i++)
		{
            if(chd[p][i])
			{
                int v=chd[p][i];
                que.push(v);
                fail[v]=chd[fail[p]][i];
                val[v]=val[v]+val[fail[v]];//对word[v]按word[fail[v]]里的内容进行处理
            }
			else
			{
                chd[p][i]=chd[fail[p]][i];
            }
        }
    }
}

int dp[110][60];
string ss[110][60];
int main()
{
	int t;
	int i,j;
	for(i=1;i<=26;i++)
		id[i]='a'+i-1;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		init();
		scanf("%d %d",&n,&m);
		getchar();
		char s[110][15];
		for(i=1;i<=m;i++)
		{
			gets(s[i]);
		}
		build_fail();
		int v[110];
		for(i=1;i<=m;i++)
			scanf("%d",&v[i]);
		for(i=1;i<=m;i++)
		{
			insert(s[i],i,v);
		}
		memset(dp,0,sizeof(dp));
		for(i=0;i<=sz-1;i++)
			ss[i][0]="";
		for(j=0;j<=n;j++)
		{
			for(i=0;i<=sz-1;i++)
			{
				for(int k=1;k<=26;k++)
					if(dp[i][j]+val[chd[i][k]]>dp[chd[i][k]][j+1])
					{
						dp[chd[i][k]][j+1]=dp[i][j]+val[chd[i][k]];
						ss[chd[i][k]][j+1]=ss[i][j]+id[k];

					}
					else if(dp[i][j]+val[chd[i][k]]==dp[chd[i][k]][j+1])
					{
						if((ss[i][j]+id[k])<ss[chd[i][k]][j+1])
							ss[chd[i][k]][j+1]=ss[i][j]+id[k];
						
					}
			}
		}
		int weight[110];
		memset(weight,0,sizeof(weight));
		for(j=0;j<=n;j++)
			for(i=0;i<=sz-1;i++)
			{
				if(dp[i][j]>weight[j])
				{
					weight[j]=dp[i][j];
				}
			}
		for(j=n;j>=1;j--)
			if(weight[j]>weight[j-1])
				break;
		int ans=j;
		string result=ss[0][ans];
		for(i=1;i<=sz-1;i++)
			if(ss[i][ans]<result)
				result=ss[i][ans];
		printf("%s\n",result.c_str());
	
	}


system("pause");
return 0;
}

hdoj2825

无限TLE。。实在改不动了。。就这样吧。
trie图+状压DP。总共10个单词不到,每个单词是否包含用0、1表示,这样状态总共不超2^10-1.dp[i][j][t]表示在trie图上走i步,处于j结点,且状态为t(压缩后的二进制串的十进制表示)时的字符串数目。状态转移见代码,有点像lrj白书上说的刷表法。

hdoj2243

TLE代码一段,写的肉流满面,居然TLE。。
这里借鉴了poj3233的思路,二分计算A+A^2+A^3+…………+A^k。据说计算A+A^2+A^3+…………+A^k.(其中A是一个矩阵,k很大)有第二种简单且更快的方法,矩阵扩大成4倍。。明天再说。。

zoj2778——trie图+矩阵快速幂

好题,trie图建好后,写出它的邻接矩阵形式,m[i][j]表示从结点i经过一步到达j的方法数(边数).注意,不能经过危险结点(何为危险结点?请参考wc的论文《trie树的改进与活用》),所以到达从点i到达危险结点的方法数设为0.这样最后结果才表示走n步(相当于写了n个字母)后没有包含单词结点的字符串数量。
注意:这里补全了结点的所有’A'——’Z'的孩子,但实际只可能转向’A'、’C'、’G'、T’,所以其他虚拟孩子不用考虑。

trie图模板

关于虚拟结点:这个知识点纠结了一个星期多,现在总算基本ok了。
对于root的不存在的孩子结点,补边,把它指向root。对于其他结点u的不存在的孩子结点c,补上边,指向fail[u]的c孩子,因为两者等效,如果fail[u]没有c孩子会怎样,没有问题,由于求解fail和补边时是bfs,所以补ch[u]..时,ch[fail][u]即使不存在,也一定补好边了。
为什么代码中对于root的孩子没有补边的代码?
因为root结点的编号是0,而ch[0][i]被初始化为0,也就是说已经指向root结点了(已经不好了)。
补边完成后:
1.trie的最下面一层叶子结点时虚拟的,不存在的,因为真实存在的结点都会补齐虚拟孩子结点。
2.对于非叶结点,每个结点的孩子都是补全的。
关于ac自动机和trie图的比较:
理解了之后感觉两者关系非常清楚:ac自动机其实是不确定性有限状态自动机,因为当结点失配要用fail回溯时可能要回溯多次。而trie图是确定性有限状态自动机,他相当于把ac自动机的可能的多次回溯变成一次,一次到达下一个状态。
为什么chd[p][i]=chd[fail[p]][i];这句一次就使得失配后(指的是p点匹配,而i点不匹配,即p没有i孩子,即ch[p][i]不存在),ch[p][i]指向了该去的结点?
答:因为计算ch[p][i]时,ch[fail[p]][i]已经计算完成,也就是ch[fail[p]][i]一定已经指向了(即被赋值为该去的结点后者其本身就存在)存在的结点。
举例来说:假设p没有c孩子,fail[p]没有c孩子,fail[fail[p]]没有c孩子,fail[fail[fail[p]]]有c孩子,那么计算ch[fail[fail[p]]]时,它被赋值为ch[fail[fail[fail[p]]]],计算ch[fail[p]]时,它被赋值为ch[fail[fail[p]]],计算ch[p]时,它被赋值为ch[fail[p]]。(上述计算过程显然是依照这个顺序进行的,因为是bfs的)可见,最终ch[p]被实际赋值为ch[fail[fail[fail[p]]]],这个ch[fail[fail[fail[p]]]]..是真实存在的结点。问题解决了。上述过程的本质就是把ac自动机的多次回溯变成了一次(有效的利用了bfs过程,这种赋值很像DP思想(确切的说是递推))
语言表达不太好,看代码把^_^
对了,还有一点:只有真实存在的点才需要fail指针,以为无论在trie图中转移到哪个点,其实每个时刻都是在一个真实存在的结点上。一个虚拟结点是不可能匹配成功的(因为根本走不到那,转移到那其实是走到了一个真实存在的结点)
匹配主串的时候,每到一个点v都要检查v、fail[v]、fail[fail[v]]……直到root,是否是单词点,道理和ac自动机相同。(一个字符串可能不是单词,但它的后缀,它的后缀的后缀……可能是单词)

ac自动机模板

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
#define maxn 10000000
typedef struct Trie{
	int count;
	int next[27];
}Trie;
Trie trie[maxn+10];
int fail[maxn+10];
int sz=1;
void init()//每次用trie前,调用一下
{
	int i;
	for(i=1;i<=26;i++)
		trie[0].next[i]=-1;
	memset(fail,0,sizeof(fail));
	trie[0].count=0;
	return;
}
void insert(char s[])
{
	int i;
	int len=strlen(s);
	int p=0;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(trie[p].next[x]!=-1)
		{
			p=trie[p].next[x];
		}
		else
		{
			trie[p].next[x]=sz++;
			p=trie[p].next[x];
			for(int j=1;j<=26;j++)
				trie[p].next[j]=-1;
			trie[p].count=0;
		}
	}
	trie[p].count=1;
	return;
}
void build_ac()
{
	queue<int> q;
	fail[0]=0;
	int i;
	for(i=1;i<=26;i++)
		if(trie[0].next[i]!=-1)
		{
			fail[trie[0].next[i]]=0;
			q.push(trie[0].next[i]);
		}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(i=1;i<=26;i++)
		{
			int v=trie[u].next[i];
			if(v!=-1)
			{
				q.push(v);
				int j=fail[u];
				while(j && trie[j].next[i]==-1)
					j=fail[j];
				if(trie[j].next[i]!=-1)
					j=trie[j].next[i];
				fail[v]=j;
			}
		}
	}
	return;
}
int find(char s[])
{
	int cnt=0;
	int i,p,cur=0;
	int len=strlen(s);
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		while(cur && trie[cur].next[x]==-1)
			cur=fail[cur];
		if(trie[cur].next[x]!=-1)
		{
			cur=trie[cur].next[x];
			p=cur;
			while(p && trie[p].count!=-1)//不管当前节点是否是单词的结尾,将它以及fail链上的结点统统标记为已访问(-1)
			{
				cnt+=trie[p].count;//点cur(当前点虽然可能不是单词结点,但是它回溯后的点可能是单词结点(即字符串S[root……cur]的后缀可能是单词结点),所以到达cur点时,可能找到的单词点不止一个,要把他们都计数,并设为-1,防止下次重复计数这些单词点)
				trie[p].count=-1;
				p=fail[p];
			}
		}
	}
	return cnt;
}
int main()
{

	init();
system("pause");
return 0;
}