题目意思 就是说一个给你 N 个单词,然后着 N 个单词中一个单词肯能包含另外一个单词,这个单词可能有包含另外一个单词,这样一直下去,做多能包含多少个单词;
思路 想想这题不用 AC 自动机会怎么做;首先对单词排序,然后用DP 的思想,后面一个单词如果包含前面那个单词,则从那个单词的最优值 +1 ,但N 太大了 不行;
转成 自动机的思想就是 先把所有字符 插入到字典数;你会发现,从根节点往后面走,知道找到一条路结束了,那么中间经过的那 N 个单词的后缀,都是符合字串包含字串的;还有一个问题就是;虽然字串包含字串,但结果不一定就是最优的;可能在这条路径的中间位置会出现他包含了一连续的字串,很明显,他所包含的那些字串不是这条路径上的;是另外一条路径上的,而结果 明显要更优;所以,这里应该取最优值不是;考虑这条路径上的每一个节点,要么他是从自己本身的这条路径上继承过来的最优值,或者是起点不是 根节点的, 但他匹配的最长公共前缀却能获的最优值;
#include<iostream> #include<stdio.h> #include<cstring> #include<algorithm> using namespace std; struct date { date *next[26],*fail; int sum,cnt; }tree[1123456],*que[1123456],*root; int res[11000],tail,head,ptr,N; date *creat_node( ) { for( int i = 0; i < 26; i++ ) tree[ptr].next[i] = NULL; tree[ptr].fail = NULL; tree[ptr].sum = 0; tree[ptr].cnt = 0; return &tree[ptr++]; } void inint( ) { tail = head = ptr = 0; root = creat_node( ); root->fail = root; } void insert( char *word,int i ) { date *temp = root; while( *word ) { int num = *word - 'a'; if( temp->next[num] == NULL ) temp->next[num] = creat_node(); temp = temp->next[num]; word++; } temp->cnt = i; } int build_AC( ) { que[tail++] = root; while( tail > head ) { date *temp = que[head++]; for( int i = 0; i < 26; i++ ) if( temp->next[i] != NULL ) { if( temp == root ) temp->next[i]->fail = root; else temp->next[i]->fail = temp->fail->next[i]; temp->next[i]->sum = max( temp->next[i]->fail->sum,temp->sum ); if( temp->next[i]->cnt ) { temp->next[i]->sum++; res[temp->next[i]->cnt] = temp->next[i]->sum; } que[tail++] = temp->next[i]; } else { if( temp == root ) temp->next[i] = root; else temp->next[i] = temp->fail->next[i]; } } int ans = 0; for( int i = 1; i <= N; i++ ) ans = max( ans,res[i] );return ans; } int main( ) { char str[1100]; while( scanf("%d",&N) &&N ) { inint( ); for( int i = 1; i <= N; i++ ) { scanf("%s",&str); insert( str,i ); } printf( "%d\n",build_AC( ) ); } return 0; }