【一道不知道名字的题】AC自动机+dp

太懒了，好久没写题解了。

Time Limit : 3000/3000ms (Java/Other)   Memory Limit : 65535/65536K (Java/Other)

Total Submission(s) : 34   Accepted Submission(s) : 8

Problem Description

Input

Output

Sample Input

2 1
a
6 2
cat tact

Sample Output

1
2

题目分析：

题意是让你构造一个长度为n的串，使得这个串中的每个字母都属于至少一个子串（即在这个子串中）。首先很明确的是，这个串中不可能有除了给定单词中出现的字母外的字母。考虑到这类构造串的问题大部分和AC自动机有关，于是可以从AC自动机的角度思考。

将给定的m个串插入字典树，然后建立自动机，自动机中每个节点保存以这个节点i为一个串的终点时串的最长长度lens[i]。

然后下面的过程考虑dp，设dp[i][j][k]表示已经处理到第i位，当前状态为ac自动机的节点j，未匹配的长度为k，枚举能转移到的节点nxt（不能转移到自动机的根，如果转移到根就说明出现了没有出现过的字母，这是不行的），则接下来有两种转移：

        dp[i + 1][nxt][k + 1] += dp[i][j][k]               lens[nxt] <= k

        dp[i + 1][nxt][0] += dp[i][j][k]                     lens[nxt] > k

我们用k=0表示完全被覆盖。

最后我们只要加上所有的i=n，k=0的状态：ans += dp[n][j][0] （0 < j < 自动机节点数）

不好意思我不知道题目在哪，这是训练赛的题^_^

本题 目的就是提供一个解题思路~

代码如下：

#include <stdio.h>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )

const int MAXN = 105 ;
const int mod = 10007 ;
const int W = 26 ;

struct Node {
	Node* next[W] ;
	Node* fail ;
	int end ;

	void init () {
		rep ( i , 0 , W ) next[i] = NULL ;
		fail = NULL ;
		end = 0 ;
	}
} ;

struct AC_automation {
	Node node[MAXN] ;
	Node* cur ;
	Node* root ;
	Node* Q[MAXN] ;
	int head , tail ;
	int dp[1005][MAXN][12] ;

	void init () {
		cur = node ;
		root = newnode () ;
	}

	Node* newnode () {
		cur->init () ;
		return cur ++ ;
	}

	void insert ( char s[] , int n ) {
		Node* now = root ;
		rep ( i , 0 , n ) {
			int x = s[i] - 'a' ;
			if ( now->next[x] == NULL ) now->next[x] = newnode () ;
			now = now->next[x] ;
		}
		now->end = n ;
	}

	void build () {
		root->fail = root ;
		head = tail = 0 ;
		rep ( i , 0 , W ) {
			if ( root->next[i] == NULL ) {
				root->next[i] = root ;
			} else {
				root->next[i]->fail = root ;
				Q[tail ++] = root->next[i] ;
			}
		}
		while ( head != tail ) {
			Node* now = Q[head ++] ;
			now->end = max ( now->end , now->fail->end ) ;
			rep ( i , 0 , W ) {
				if ( now->next[i] == NULL ) {
					now->next[i] = now->fail->next[i] ;
				} else {
					now->next[i]->fail = now->fail->next[i] ;
					Q[tail ++] = now->next[i] ;
				}
			}
		}
	}

	void add ( int& x , int y ) {
		x += y ;
		if ( x >= mod ) x %= mod ;
	}

	void solve ( int n ) {
		int m = cur - root ;
		clr ( dp , 0 ) ;
		dp[0][0][0] = 1 ;
		For ( i , 1 , n ) {
			rep ( j , 0 , m ) {
				rep ( k , 0 , 10 ) if ( dp[i - 1][j][k] ) {
					rep ( w , 0 , W ) {
						int nxt = node[j].next[w] - root ;
						if ( !nxt ) continue ;
						if ( node[nxt].end < k + 1 ) add ( dp[i][nxt][k + 1] , dp[i - 1][j][k] ) ;
						else add ( dp[i][nxt][0] , dp[i - 1][j][k] ) ;
					}
				}
			}
		}
		int ans = 0 ;
		rep ( i , 0 , m ) add ( ans , dp[n][i][0] ) ;
		printf ( "%dn" , ans ) ;
	}
} ;


AC_automation ac ;
char s[MAXN] ;
int n , m ;

void solve () {
	ac.init () ;
	rep ( i , 0 , m ) {
		scanf ( "%s" , s ) ;
		int len = strlen ( s ) ;
		ac.insert ( s , len ) ;
	}
	ac.build () ;
	ac.solve ( n ) ;
}

int main () {
	while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;
	return 0 ;
}

最后

以上就是疯狂凉面为你收集整理的【一道不知道名字的题】AC自动机+dp的全部内容，希望文章能够帮你解决【一道不知道名字的题】AC自动机+dp所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。