程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3341 ac自動機+hash+dp

hdu 3341 ac自動機+hash+dp

編輯：C++入門知識

Lost's revenge

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 2607 Accepted Submission(s): 651

Problem Description Lost and AekdyCoin are friends. They always play "number game"(A boring game based on number theory) together. We all know that AekdyCoin is the man called "nuclear weapon of FZU,descendant of Jingrun", because of his talent in the field of number theory. So Lost had never won the game. He was so ashamed and angry, but he didn't know how to improve his level of number theory.

One noon, when Lost was lying on the bed, the Spring Brother poster on the wall(Lost is a believer of Spring Brother) said hello to him! Spring Brother said, "I'm Spring Brother, and I saw AekdyCoin shames you again and again. I can't bear my believers were being bullied. Now, I give you a chance to rearrange your gene sequences to defeat AekdyCoin!".

It's soooo crazy and unbelievable to rearrange the gene sequences, but Lost has no choice. He knows some genes called "number theory gene" will affect one "level of number theory". And two of the same kind of gene in different position in the gene sequences will affect two "level of number theory", even though they overlap each other. There is nothing but revenge in his mind. So he needs you help to calculate the most "level of number theory" after rearrangement.
Input There are less than 30 testcases.
For each testcase, first line is number of "number theory gene" N(1<=N<=50). N=0 denotes the end of the input file.
Next N lines means the "number theory gene", and the length of every "number theory gene" is no more than 10.
The last line is Lost's gene sequences, its length is also less or equal 40.
All genes and gene sequences are only contains capital letter ACGT.

Output For each testcase, output the case number(start with 1) and the most "level of number theory" with format like the sample output.
Sample Input

3
AC
CG
GT
CGAT
1
AA
AAA
0

Sample Output

Case 1: 3
Case 2: 2

Author Qinz@XDU
Source HDOJ Monthly Contest – 2010.03.06

題意：給定n個特定的串，最後給定一個串，讓重新組合，使得含有的上面特定的串最多。

首先肯定需要建立ac自動機，然後就是dp，這道題在dp的時候需要一定的處理，不能直接搞，學習別人的思路，采用hash的方法，將死個字符出現的次數映射成數字，且保證了不會出現狀態的重復，好神奇，然後就是一個dp的過程了。

代碼：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-7 0:28:06
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
struct Trie{
	int next[550][4],fail[550],end[550];
	int root,L;
	int newnode(){
		for(int i=0;i<4;i++)
			next[L][i]=-1;
		end[L++]=0;
		return L-1;
	}
	void init(){
		L=0;
		root=newnode();
	}
	int id(char ch){
		if(ch=='A')return 0;
		if(ch=='T')return 1;
		if(ch=='C')return 2;
		return 3;
	}
	void insert(char *str){
		int len=strlen(str);
		int now=root;
		for(int i=0;i q;
		fail[root]=root;
		for(int i=0;i<4;i++){
			if(next[root][i]==-1)
				next[root][i]=root;
			else {
				fail[next[root][i]]=root;
				q.push(next[root][i]);
			}
		}
		while(!q.empty()){
			int now=q.front();
			q.pop();
			end[now]+=end[fail[now]];
			for(int i=0;i<4;i++){
				if(next[now][i]==-1)
					next[now][i]=next[fail[now]][i];
				else {
					fail[next[now][i]]=next[fail[now]][i];
					q.push(next[now][i]);
				}
			}
		}
	}
	int dp[11*11*11*11+10][550];
	int num[5],ss[5],hash[6];
	int solve(char *str){
		memset(hash,0,sizeof(hash));
		memset(num,0,sizeof(num));
		int len=strlen(str);
		for(int i=0;inum[0]||ss[1]>num[1]||ss[2]>num[2]||ss[3]>num[3])continue;
			for(int j=0;j