Title Description :
YXY I found that many words in the computer are abbreviations , Such as GDB, It's the full name Gnu DeBug Abbreviation . however , Sometimes the full name of the abbreviation is not fixed , Such as abbreviation LINUX, It can be understood as :
(1)LINus's UniX (2)LINUs's miniX (3)Linux Is Not UniX
Now? YXY Give a word abbreviation , And a fixed full name ( It's made up of several words , Separate... With spaces ). There may be invalid words in the full name , It needs to be ignored , A legal abbreviation requires at least one of every valid word
Characters appear in abbreviations , Abbreviations must appear in the full name in order . For a given abbreviation and a fixed full name , Ask how many ways to explain . The explanation is the position of each letter of the abbreviation in each valid word in the full name , There's a letter in a different position , I think it's a different interpretation .

Input format :
Enter one on the first line N, Express N Two invalid words ; Next N Each line describes an invalid word made up of lowercase letters ; And then there are some questions , Give the abbreviation first ( Only capital letters ), Then give a full name . read
Enter into “LAST CASE” end .

Output format :
For each query, output the abbreviation first , If the current abbreviation is illegal . The output “is not a valid abbreviation”, Otherwise output “can be formed in i ways”(i Means the number of interpretation methods ).

The sample input :

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

Sample output :

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

Data range : 1<=N<=100, The length of a string per line does not exceed 150, Ask no more than 20, Given the data, calculate
The number of final plans to come is not more than 10^9.

The data range is very small , This is a violent revision + commonly DP

Post code :

 #include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
inline int read()
{
int x=,f=;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-;c=getchar();}
while(isdigit(c)){x=x*+c-'';c=getchar();}
return x*f;
}
int n,l1,l2,l3;
char s[],sc[][],mb[],t[];
bool judge(char *a,char *b)
{
int x=strlen(a),y=strlen(b);
if(x!=y)return ;
for(int i=;i<x;i++)
if(a[i]!=b[i])return ;
return ;
}
int main()
{
freopen("abbr.in","r",stdin);
freopen("abbr.out","w",stdout);
n=read();
for(int i=;i<n;i++)scanf("%s",sc[i]);
cin.getline(s,);
while()
{
char tmp[];
memset(tmp,,sizeof(tmp));
memset(mb,,sizeof(mb));
memset(s,,sizeof(s));
cin.getline(tmp,);
if(!strcmp(tmp,"LAST CASE"))break;
int l0=strlen(tmp);;bool ok=;
l1=l2=l3=;
int i = ;
while(tmp[i] != ' ') mb[l1++] = tmp[i++];
for(i++; i < l0; i++) s[l2++] = tmp[i];
// printf("%s\n%s\n", mb, s);
ok=;
int st=,en=,now=;
bool had[];
memset(had,,sizeof(had));
memset(tmp,,sizeof(tmp));
memset(t, , sizeof(t));
for(i = ; i < l2;) {
char tw[]; int tcnt = ;
while(i < l2 && s[i] != ' ') {
tw[tcnt++] = s[i];
i++;
}
i++;
tw[tcnt] = ;
bool ok = ;
for(int j = ; j < n; j++) if(!strcmp(sc[j], tw)) {
ok = ; break;
}
if(!ok) continue;
for(int j = ; j < tcnt; j++) t[l3++] = tw[j];
t[l3++] = ' ';
}
l3--;
// printf("%s %s\n", mb, t);
int cnt=;
for(int i=;i<l3;i++) if(t[i]==' ')cnt++;
if(cnt>l1)
{
printf("%s is not a valid abbreviation\n",mb);
continue;
}
int dp[][][];
memset(dp,,sizeof(dp));
for(int i=l1;i>=;i--)mb[i]=mb[i-];
for(int i=l3;i>=;i--)t[i]=t[i-];
// printf("new: %s %s\n", mb + 1, t + 1);
dp[][][]=;
for(int i=;i<=l3;i++)
{
if(t[i]==' ')continue;
for(int j=;j<=min(i,l1);j++)
{
// printf("%d %d: %d %d\n", i, j, dp[i][j][0], dp[i][j][1]);
if(t[i+]==' ')
{
if(t[i+]-'a'==mb[j+]-'A')dp[i+][j+][]+=dp[i][j][];
dp[i+][j][]+=dp[i][j][];
continue;
}
if(t[i+]-'a'==mb[j+]-'A')dp[i+][j+][]+=(dp[i][j][]+dp[i][j][]);
dp[i+][j][]+=dp[i][j][];dp[i+][j][]+=dp[i][j][];
}
}
for(int i=;i<=l1;i++)printf("%c",mb[i]);
if(!dp[l3][l1][])printf(" is not a valid abbreviation\n");
else printf(" can be formed in %d ways\n",dp[l3][l1][]); }
return ;
}

Abbreviations of words (abbr.cpp) More articles about the daily question

  1. [LeetCode] Minimum Unique Word Abbreviation The shortest, unique abbreviation

    A string such as "word" contains the following abbreviations: ["word", "1or ...

  2. [LeetCode] Valid Word Abbreviation Verify abbreviations

    Given a non-empty string s and an abbreviation abbr, return whether the string matches with the give ...

  3. [LeetCode] 288.Unique Word Abbreviation Unique abbreviations

    An abbreviation of a word follows the form <first letter><number><last letter>. Be ...

  4. P1624 Abbreviations of words

    P1624 Abbreviations of words Title Description Tree tree found that many computer words are abbreviations , Such as GDB It's the full name Gnu DeBug Abbreviation . however , Sometimes the full name of the abbreviation is not fixed , Such as abbreviation LINUX It can be understood as : (1) LINus’s U ...

  5. 【Java A daily topic 】20170106

    20170105 For problem analysis, please click below today's questions "[Java A daily topic ]20170106" see ( The problem is solved in the official account , official account ID:weknow619) package Jan2017; ...

  6. 【Java A daily topic 】20170105

    20170104 For problem analysis, please click below today's questions "[Java A daily topic ]20170105" see ( The problem is solved in the official account , official account ID:weknow619) package Jan2017; ...

  7. 【Java A daily topic 】20170104

    20170103 For problem analysis, please click below today's questions "[Java A daily topic ]20170104" see ( The problem is solved in the official account , official account ID:weknow619) package Jan2017; ...

  8. 【Java A daily topic 】20170103

    20161230 For problem analysis, please click below today's questions "[Java A daily topic ]20170103" see ( The problem is solved in the official account , official account ID:weknow619) package Jan2017; ...

  9. 【Java A daily topic 】20161230

    // 20161229 For problem analysis, please click below today's questions "[Java A daily topic ]20161230" see ( The problem is solved in the official account , official account ID:weknow619)package Dec2016 ...

Random recommendation

  1. java Count the number of string words

    In some projects, you may need to count the words in a string , I wrote a simple one here demo, Students in need can take a look . I didn't write a podcast very much , If there's something wrong , You hit me Don't talk nonsense, just paste the code : Implementation code ...

  2. Manual installation eclipse Of svn plug-in unit Subversive and Subversive SVN Connectors

      0. Download configuration jdk link :http://pan.baidu.com/s/1miIVuic password :mwo7 To configure JAVA_HOME .JRE_HOME 1 download eclipse       ecli ...

  3. Boolean.parseBoolean(&quot;true&quot;) and Boolean.getBoolean(&quot;true&quot;); The difference and usage of

    Proper use :boolean repeatIndicator = Boolean.valueOf("true").booleanValue(); Or you can use it Boolean.parse ...

  4. Day 353 how can I insist

    I bought a quilt today , Make do with it , It's not so good . I went to North China Electric Power University in the afternoon , I had a chat with Liu Lu , Or too much talk .. Not good. . And bought barrels of oil and rice .. Take a shower , sleep , It's a fast day .

  5. js File upload , Delete effect

    design sketch : At first : Click button " After choosing more ", You can add a lot of selection files : Click button " Delete " after : Implementation code : <!DOCTYPE html><html ...

  6. solve tomcat Begin to appear in production environments was not found on the java.library.path:xxx

    As you can see ,Eclipse Start in tomcat When not found on the java.library.path Etc . Can be downloaded tomcat-native-1.1.32-win32-bin ...

  7. JavaScript( Abandon the pit for the time being ...)

    Simple data type : String type . Boolean type . Numerical type Variable names can contain Numbers . Letter . Underline .$, But don't start with a number , Case sensitive , It can't be JavaScript keyword . Avoid reserved words //JavaScript Reserved words break e ...

  8. java.lang.RuntimeException: Can&#39;t create handler inside thread that has not called Looper.prepare()

  9. Python Cross platform packaging

    about pyinstaller, It can be finished in windows,linux, and mac Under the python Script Compilation , Generate exe,elf,.app file : 1. Usage method : stay pyinstaller Download on the official website of , It's usually the source code ...

  10. HTML5 New characteristics : Range style

    The source of the original text is :http://blog.csdn.net/hfahe/article/details/7381141        Chromium Recently, a HTML5 New features : Range style , Also known as < ...