竞赛题
C  Problem C

Time Limit:1000MS  Memory Limit:65535K

题型: 编程题   语言: 无限制
描述

    我们都知道，学习英语单词最好的方法就是在相应的句子和语言环境中学习。小W最近定下了一个学习单词的计划，他要背n个单词，但他想通过背一篇文章中的一段来记住这些单词。

假定现在小W手中有一篇包含m个单词的文章，他想在文章中找出连续的一段，其中包含最多的他所要背的单词(重复的只算一个)，并且使这段连续的单词长度最短。这样他就可以用尽量短的时间学习尽可能多的单词了。

 

输入格式

    第1行一个数n (1≤n≤1000)

    接下来n行每行是一个长度不超过10的字符串，表示一个要背的单词。

    接着是一个数m (1≤m≤100000 )

然后是m行长度不超过10的字符串，每个表示文章中的一个单词。
输出格式

    输出文件共2行。第1行为文章中最多包含的要背的单词数，第2行表示在文章中包含最多要背单词的最短的连续段的长度。
输入样例

3
hot
dog
milk
5
hot
dog
dog
milk
hot

输出样例

3
3

Provider
200831000423

哥屋恩

不要求代码   只要求给出思路  或者用到什么算法即可

又是你们学校的题？也不能去测试，有些乏味了。 这个算法时间复杂度不超过O(m)。

要测试么，我给你账号就行啦
不过这个题没，老师没把他上去。我问问怎么办吧

要不你加我QQ吧  1004573547

你们学校的OJ外网能访问得到？如果能，那不妨帮我申请一个帐号。QQ我几乎不用，所以意义不大。

题目要求的串的找法可以这么做，设f(i,j)包含了最多的待记单词，i、j分别表示它在原串中的左右边界

如果f(i, j - 1)中包含f(j, j)，那么f(i, j - 1)中也包含了最多的待记单词

同理，如果f(i + 1, j)中包含f(i, i)，那么f(i + 1, j)中也包含最多的待记单词

简单的动态规划应用。

目前不能够申请账号。。。只有本校学生才可以用学号注册
上面那个题目http://www.soj.me/submit.php?problem_id=1222
有

我用最笨的方法做出来测试没错 提交不是超时 是错误
#include <iostream>
#include<cstring>
using namespace std;
  int c[100020],visit[100020];
void EN(char *a,char *b,int n,int k)
{

    if(strcmp(a,b)==0)   c[k]=n;

}

void dfs(int n,int i,int m)
{

}
int main()
{
  char a[1002][12],b[100002][12];

  int n,m;
  cin>>n;
  memset(c,0,sizeof(c));
  for(int i=0;i<n;i++)
    cin>>a[i];
  cin>>m;
 for(int i=0;i<m;i++)
    cin>>b[i];
for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
       EN(a[i],b[j],i+1,j+1);

int sum=0;
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
{
   if(c[j]==i) {sum++;//  cout<<c[j]<<endl;
   break;  }
}
//cout<<sum<<"ijuio"<<endl;
int max=0,maxstr=2*m;
int flag;
for(int i=1;i<=m;i++){
      memset(visit,0,sizeof(visit));
      int  maxnum=0;max=0;
       flag=0;
    for(int j=i;j<=m;j++)
    {
        if(c[j]>0&&!visit[c[j]])
        {  visit[c[j]]=1;
            max++;   //cout<<"sss"<<max<<' '<<i<<endl;
        }
//cout<<"sss"<<max<<' '<<i<<endl;
        maxnum++;
    if(max==sum) {flag=1; break;}
    }
    if(flag&&maxnum<maxstr) maxstr=maxnum;
}
cout<<sum<<'\n'<<maxstr<<endl;


    return 0;
}

DFS那个是没用的