Morse code（多模式串匹配）

链接：https://ac.nowcoder.com/acm/contest/3665/E
来源：牛客网

题目描述

Morse code is a character encoding scheme used in telecommunication that encodes text characters as standardized sequences of two different signal durations called dots and dashes or dits and dahs. Morse code is named for Samuel F. B. Morse, an inventor of the telegraph.

Space is used to split Morse code, but if all spaces are lost, then the Morse code may have many meanings.For example: ".-. "can be translated to "AE"or "EN"or "R", but the string translated from Morse code can’t contain ’E’ and ’T’. So "R"is the longest string it can represent. Now hery is given a Morse code, he wants to know the length of the longest string it can represent.

输入描述:

The first line is an integer T, the number of test cases.
Next T lines, each line contains a Morse code consist of ’.’ and ’-’.
(1 ≤ T ≤ 100, the number of characters input will not exceed $10^6).$

输出描述:

For each Morse code ,output the length of the longest string it can represent.

示例1

输入

2
..--.-.
--.-.--

输出

3
3

长度为

此处给出

 1 作者：Uncle_drew
 2 链接：https://ac.nowcoder.com/discuss/363155?type=101
 3 来源：牛客网
 4 
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 const int maxn=1e6+10;
 8 map<int,int>mp;
 9 string code[100];
10 char s[maxn];
11 int dp[maxn];
12 void init(){
13     code[1]=".-";   code[2]="-..."; code[3]="-.-."; code[4]="-..";
14     code[5]="..-."; code[6]="--.";  code[7]="....";
15     code[8]="..";   code[9]=".---"; code[10]="-.-"; code[11]=".-..";
16     code[12]="--";  code[13]="-.";  code[14]="---"; code[15]=".--.";
17     code[16]="--.-";code[17]=".-."; code[18]="...";
18     code[19]="..-"; code[20]="...-"; code[21]=".--";code[22]="-..-";
19     code[23]="-.--"; code[24]="--..";
20     for(int i=1;i<=24;i++){
21         int num=0;
22         for(int j=0;j<code[i].length();j++) num=num*100+code[i][j];
23         mp[num]++;
24     }
25 }
26 int cal(int a,int b){
27     int num=0;
28     for(int i=a;i<=b;i++) num=num*100+s[i];
29     return mp[num]?1:0;
30 }
31 void solve(){
32     scanf("%s",s);
33     int n=strlen(s);
34     for(int i=0;i<n;i++){
35         dp[i]=0;
36         for(int j=1;j<=4;j++){
37             int y=i-j;
38             dp[i]=max(dp[i],dp[i-j]+cal(i-j+1,i));
39         }
40     }
41     printf("%d
",dp[n-1]);
42 }
43 int main()
44 {
45     init();
46     int t;
47     scanf("%d",&t);
48     while(t--){
49         solve();
50     }
51     return 0;
52 }