P1624 单词缩写

题目描述

树树发现好多计算机中的单词都是缩写，如GDB是全称Gnu DeBug的缩写。但是，有时候缩写对应的全称会不固定，如缩写LINUX可以理解为：

（1） LINus’s UniX

（2） LINUs’s miniX

（3） Linux Is Not UniX

现在树树给出一个单词缩写，以及一个固定的全称（若干个单词组成，空格隔开）。全

称中可能会有无效的单词，需要忽略掉，一个合法缩写要求每个有效单词中至少有一个字符出现在缩写中，所写必须按顺序出现在全称中。

对于给定的缩写和一个固定的全称，问有多少种解释方法？解释方法为所写的每个字母在全称每个有效单词中出现的位置，有一个字母位置不同，就认为是不同的解释方法。

输入输出格式

输入格式：

第一行输入一个N，表示有N个无效单词；

接下来N行分别描述一个由小写字母组成的无效单词；

最后是若干个询问，先给出缩写（只有大写字母），然后给出一个全称，读入以“LAST CASE”结束。

[数据规模]

1≤N≤100，每行字符串长度不超过150，询问次数不超过20，最后方案数不超过10^9。

输出格式：

对于每个询问先输出缩写，如果当前缩写不合法，则输出“is not a valid abbreviation”,否则输出“can be formaed in i ways”(i表示解释方法数)

输入输出样例

输入样例#1：复制

2
and
of
ACM academy of computer makers
RADAR radio detection and ranging
LAST CASE

输出样例#1：复制

ACM can be formed in 2 ways
RADAR is not a valid abbreviation

洛谷题解

先暴力去掉所有的单词，只对有效单词进行计算。

dp[i][j]表示前i个单词使用了前j个大写字母的方案数

初始条件dp[0][0]=1

转移：若第i个单词使用第j到第j+k个大写字母的方案数为temp[k]

则dp[i][j+k]=dp[i-1][j-1]*temp[k]

最终ans=dp[n][m]

时间复杂度Ｏ（Ｌ１＊Ｎ＊Ｌ２＊Ｌ２）

空间复杂度Ｏ(Ｌ１*Ｎ*Ｌ２)

L1缩写长度 N全称中单词的个数 L2全称中一个单词的长度

这属于两个串匹配的问题，就一个前i，一个前j就好，反正是找子问题。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 char w[101][150];
 7 char s[150],let[150];
 8 char over[9]={'L','A','S','T',' ','C','A','S','E'};
 9 struct word
10 {
11     char c[150];
12     int l;
13 }a[150];
14 int t,n,m,len;
15 int dp[100][150],temp[150];
16 bool Case_is_Over()
17 {
18     for (int i=0;i<=8;i++)
19         if (s[i]!=over[i]) return false;
20     return true;
21 }
22 int main()
23 {
24     freopen("abbr.in","r",stdin);
25     freopen("abbr.out","w",stdout);
26     scanf("%d
",&t);
27     for (int i=1;i<=t;i++) scanf("%s",w[i]);
28     while (233)
29     {
30         char ch=getchar();len=0;
31         while ( ! ( (ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z') || ch==' ' ) ) ch=getchar();
32         while ( (ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z') || ch==' ' ) s[len++]=ch,ch=getchar();
33         n=m=0;//设每个询问有n个单词，m个大写字母
34         if (Case_is_Over()) break;
35         int p=0;
36         for (int i=1;i<150;i++) memset(a[i].c,0,sizeof(a[i].c)),a[i].l=0;
37         while (s[p]>='A'&&s[p]<='Z')
38         {
39             printf("%c",s[p]);
40             let[++m]=s[p]+32;
41             p++;
42         }
43         p++;
44         while (p<len)
45         {
46             n++;
47             while (s[p]>='a'&&s[p]<='z')
48             {
49                 a[n].c[a[n].l++]=s[p];
50                 p++;
51             }
52             for (int i=1;i<=t;i++)
53                 if (strcmp(w[i],a[n].c)==0)
54                 {
55                     memset(a[n].c,0,sizeof(a[n].c));
56                     a[n].l=0;
57                     n--;break;
58                 }
59             p++;
60         }
61         memset(dp,0,sizeof(dp));
62         dp[0][0]=1;
63         for (int i=1;i<=n;i++) //枚举单词
64             for (int j=i;j<=i+m-n;j++) //枚举当前单词使用大写字母的起始位置
65             {
66                 memset(temp,0,sizeof(temp));
67                 for (int p=0;p<a[i].l;p++) //第i个单词的第p个位置
68                     for (int k=min(i+m-n-j,p);k>=0;k--) //恰好等于第j+k个大写字母
69                         if (let[j+k]==a[i].c[p])
70                             if (k) temp[k]+=temp[k-1];
71                             else temp[k]++;
72                 for (int k=i+m-n-j;k>=0;k--)
73                     dp[i][j+k]+=dp[i-1][j-1]*temp[k];
74             }
75         if (dp[n][m]) printf(" can be formed in %d ways
",dp[n][m]);
76         else printf(" is not a valid abbreviation
");
77     }
78     return 0;
79 }

看大家都是N^4或N³算法，N²算法还没有，~~赶紧水一发~~

基本思路:

把所有串连接起来，记录每个串的尾后位置，

设f[k][i]表示现在在处理缩写的第K个字符，在大字符串中第I个位置对前面字符的总贡献数，则f[k][i]=Σf[k-1][j]，

其中j表示满足条件的前一个缩写字符。其中满足条件的定义为“无空缺单词，且是前一个字母”。则答案为Σf[最后一个字符][j],(1<=j<=n)。

为避免出现同一字母出现位置的不同，用一个数组进行标记即可。

标记要一次打完才能更新！！！

  1 #include<bits/stdc++.h>
  2 #define RG register
  3 using namespace std;
  4 
  5 int n;
  6 char a[110][200];//无效单词
  7 char c1[200];
  8 char c[200];
  9 char all[200][200];//有效单词
 10 int ma[26][200];//每个字母的有效位置
 11 int tag[200];
 12 int tag1[200];//两个标记
 13 int cut[200];//单词的尾后位置
 14 int sum[26];//出现的次数
 15 int f[200][200];//dp数组
 16 
 17 int main()
 18 {
 19     scanf("%d
",&n);
 20     for(RG int i=1;i<=n;i++)
 21     {
 22         scanf("%s",a[i]);
 23     }
 24     scanf("%s",c1);
 25     while(1)
 26     {
 27         RG int i_1_1=1;
 28         strcpy(c,c1);
 29         if(strcmp(c,"LAST")==0)
 30         {
 31             scanf("%s",all[i_1_1++]);
 32             if(strcmp(all[i_1_1-1],"CASE")==0) break;
 33         }
 34         while(cin>>all[i_1_1++])
 35         {
 36             RG int j=0;
 37             int len=strlen(all[i_1_1-1]);
 38             while(all[i_1_1-1][j]<'a'&&j<len) j++;
 39             if(j>=len)
 40             {
 41                 strcpy(c1,all[i_1_1-1]);
 42                 i_1_1--;
 43                 break;
 44             }
 45             else
 46             {
 47                 for(RG int i=1;i<=n;i++)
 48                 {
 49                     if(strcmp(a[i],all[i_1_1-1])==0)
 50                     {
 51                         i_1_1--;
 52                         break;
 53                     }
 54                 }
 55             }
 56         }
 57         i_1_1--;
 58         printf("%s ",c);
 59         int len=strlen(c);
 60         for(RG int i=0;i<len;i++)
 61         {
 62             c[i]=c[i]+32;
 63         }
 64         //读入
 65         if(len<i_1_1)//分类讨论
 66         {
 67             puts("is not a valid abbreviation");
 68         }
 69         else if(len==i_1_1)
 70         {
 71             int ans=1;
 72             for(RG int i=0;i<len;i++)
 73             {
 74                 int len2=strlen(all[i+1]);
 75                 RG int tmp=0;
 76                 for(RG int j=0;j<len2;j++)
 77                 {
 78                     if(all[i+1][j]==c[i]) tmp++;
 79                 }
 80                 if(tmp) ans*=tmp;
 81                 else
 82                 {
 83                     puts("is not a valid abbreviation");
 84                     break;
 85                 }
 86             }
 87             printf("can be formed in %d ways
",ans);
 88         }
 89         else //重点
 90         {
 91             memset(sum,0,sizeof(sum));
 92             memset(f,0,sizeof(f));
 93             memset(tag,0,sizeof(tag));
 94             memset(cut,0,sizeof(cut));
 95             memset(ma,0,sizeof(ma));
 96             int cz=strlen(all[1]);
 97             for(int i=2;i<=i_1_1;i++)
 98             {
 99                  strcpy(all[1]+cz,all[i]);
100                  cut[i-1]=cz;
101                  cz=strlen(all[1]);
102             }
103             //连串
104             cut[i_1_1]=cz;
105             for(int i=0;i<cz;i++)
106             {
107                 int j=all[1][i]-'a';
108                 ma[j][++sum[j]]=i;
109             }
110             //记字母位置
111             for(int k=0;k<len;k++)
112             {
113                 int id=c[k]-'a';
114                 int ci=min(k+1,i_1_1);
115                 int ti=1;
116                 for(int i=0;i<cz;i++)
117                 {
118                     tag1[i]=tag[i];
119                 }//备份
120                 for(int i=1;i<=sum[id]&&ma[id][i]<cut[ci];i++)
121                 {
122                     while(ma[id][i]>=cut[ti]) ti++;
123                     if(i_1_1-ti>len-k-1) continue;
124                     if(k==0)
125                     {
126                         tag1[ma[id][i]]=0;//标记
127                         f[k][i]=1;//初始值
128                     }
129                     else
130                     {
131                         int t=c[k-1]-'a';
132                         for(int j=1;j<=sum[t];j++)
133                         {
134                             if(ma[t][j]<ma[id][i]&&ma[t][j]>=cut[ti-2]&&tag[ma[t][j]]==k-1)
135                             {
136                                 f[k][i]+=f[k-1][j];//转移
137                                 tag1[ma[id][i]]=k;//标记×2
138                             }
139                         }
140                     }
141                 }
142                 for(int i=0;i<cz;i++)
143                 {
144                     tag[i]=tag1[i];//备份
145                 }
146             }
147             int ans=0;
148             for(int i=1;i<=sum[c[len-1]-'a'];i++)
149             {
150                 ans+=f[len-1][i];//求和
151             }
152             if(ans)
153             {
154                 printf("can be formed in %d ways
",ans);
155             }
156             else puts("is not a valid abbreviation");
157         }
158     }
159     return 0;
160 }