首页 > 搜索 > BFS搜索 > hdu 2243 考研路茫茫――单词情结-BFS-[解题报告]C++
2014
01-04

hdu 2243 考研路茫茫――单词情结-BFS-[解题报告]C++

考研路茫茫――单词情结

问题描述 :

背单词,始终是复习英语的重要环节。在荒废了3年大学生涯后,Lele也终于要开始背单词了。
一天,Lele在某本单词书上看到了一个根据词根来背单词的方法。比如"ab",放在单词前一般表示"相反,变坏,离去"等。

于是Lele想,如果背了N个词根,那这些词根到底会不会在单词里出现呢。更确切的描述是:长度不超过L,只由小写字母组成的,至少包含一个词根的单词,一共可能有多少个呢?这里就不考虑单词是否有实际意义。

比如一共有2个词根 aa 和 ab ,则可能存在104个长度不超过3的单词,分别为
(2个) aa,ab,
(26个)aaa,aab,aac…aaz,
(26个)aba,abb,abc…abz,
(25个)baa,caa,daa…zaa,
(25个)bab,cab,dab…zab。

这个只是很小的情况。而对于其他复杂点的情况,Lele实在是数不出来了,现在就请你帮帮他。

输入:

本题目包含多组数据,请处理到文件结束。
每组数据占两行。
第一行有两个正整数N和L。(0<N<6,0<L<2^31)
第二行有N个词根,每个词根仅由小写字母组成,长度不超过5。两个词根中间用一个空格分隔开。

输出:

本题目包含多组数据,请处理到文件结束。
每组数据占两行。
第一行有两个正整数N和L。(0<N<6,0<L<2^31)
第二行有N个词根,每个词根仅由小写字母组成,长度不超过5。两个词根中间用一个空格分隔开。

样例输入:

2 3
aa ab
1 2
a

样例输出:

104
52

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2243

题目大意:问长度为1~N的串中包含了模式串的串总共有几个。

题目思路:求出长度不大于l的包含模式串的字符串数,方法是改求不包含模式串的字符串总数,当然先要处理出总的字符串个数,可以用矩阵也可以用二分幂和的方法。而求不包含模式串的字符串数同样是构造矩阵,同时还要建立一个虚结点,储存长度小于l的不包含模式串的字符串总数。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define uint unsigned __int64
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int q[6*6],cnt;
int hash[36];
uint a[25][25],b[25][25],c[25][25],ans;
struct node
{
    int cnt,fail;
    int next[26];
    void init()
    {
        cnt=fail=0;
        memset(next,0,sizeof(next));
    }
}tri[6*6];
void insert(char *s)
{
    int i,p,x;
    p=0;
    for(i=0;s[i];i++)
    {
        x=s[i]-'a';
        if(!tri[p].next[x])
        {
            tri[++cnt].init();
            tri[p].next[x]=cnt;
        }
        p=tri[p].next[x];
    }
    tri[p].cnt++;
}
void bfs()
{
    int i,p=0,suf,head=0,tail=0;
    for(i=0;i<26;i++)
    {
        if(tri[0].next[i])
        {
            q[tail++]=tri[0].next[i];
            tri[q[tail-1]].fail=0;
        }
    }
    while(head<tail)
    {
        p=q[head++];suf=tri[p].fail;
        tri[p].cnt+=tri[suf].cnt;
        for(i=0;i<26;i++)
        {
            if(tri[p].next[i])
            {
                q[tail++]=tri[p].next[i];
                tri[q[tail-1]].fail=tri[suf].next[i];
            }
            else
                tri[p].next[i]=tri[suf].next[i];
        }
    }
    tri[cnt+1].cnt=0;
    memset(b,0,sizeof(b));
    int tmp=0;
    for(i=0;i<=cnt+1;i++)
    {
        if(!tri[i].cnt)
        {
            hash[i]=tmp++;
        }
    }
    for(i=0;i<=cnt;i++)
    {
        if(tri[i].cnt)
            continue;
        else
        {
            b[hash[i]][hash[cnt+1]]++;
            for(int j=0;j<26;j++)
            {
                int tmp=tri[i].next[j];
                if(!tri[tmp].cnt)
                    b[hash[i]][hash[tmp]]++;
            }
        }
    }
    cnt++;
    b[hash[cnt]][hash[cnt]]=1;
    cnt=tmp-1;
}
void run(uint a[][25],uint b[][25],uint c[][25],int cnt)
{
    int i,j,k;
    for(i=0;i<=cnt;i++)
        for(j=0;j<=cnt;j++)
        {
            c[i][j]=0;
            for(k=0;k<=cnt;k++)
                c[i][j]+=a[i][k]*b[k][j];
        }
    for(i=0;i<=cnt;i++)
        for(j=0;j<=cnt;j++)
            a[i][j]=c[i][j];
}
void getsum(int n)
{
    a[0][0]=0;a[0][1]=26;
    a[1][0]=0;a[1][1]=0;
    b[0][0]=26;b[0][1]=0;
    b[1][0]=1;b[1][1]=1;
    ans=0;
    while(n)
    {
        if(n&1)
            run(a,b,c,1);
        n>>=1;
        run(b,b,c,1);
    }
    ans=a[0][0];
}
void solve(int n)
{
    memset(a,0,sizeof(a));
    a[0][0]=1;
    while(n)
    {
        if(n&1)
            run(a,b,c,cnt);
        n>>=1;
        run(b,b,c,cnt);
    }
    for(int i=0;i<=cnt;i++)
        ans-=a[0][i];
}
int main()
{
    int n,l;
    char s[10];
    while(scanf("%d%d",&n,&l)!=EOF)
    {
        cnt=0;
        tri[0].init();
        while(n--)
        {
            scanf("%s",s);
            insert(s);
        }
        getsum(l);
        bfs();
        solve(l);
        printf("%I64u\n",ans+1);
    }
}

 

解题转自:http://blog.csdn.net/wings_of_liberty/article/details/7600610


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  3. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测