A39216. 谜【
题目描述
谜
【题目描述】
二战期间，德军使用一种名为“Enigma”的密码机。这个密码机最终被盟军破解的关键之一，是来自于使用它的人的习惯。德军每天发送的电报中，会有很多重复的词语，比如问候语、结尾的落款、每天的天气等等。盟军的破解人员把这些重复出现的词语称作“crib”。知道了“crib”，还要知道“crib”在密文中的什么位置。由于“Enigma”是通过电路加密，所以一
个字母加密后绝对不会仍然是自身，这个特性可以帮助我们定位“crib”的位置。
例如盟军截获了一条密文"XEQFTWRWEVTRES"，并且我们猜测原文中可能含有"WETTER"这个词。因为字母绝对不会被加密成自身，所以当我们将"WETTER"这个词和密文去比对，就可以找到这个词可能的位置。
在下面这个位置时，"WETTER"和密文对应的每个位置的字母都不相同，所以这条密文的原文中可能含有"WETTER"。
一条密文中可能含有不止一种“crib”，同一种“crib”也可能出现多次，“crib”所占据的位置不能有重叠。给出所有可能的“crib”和一条密文，你要求出这条密文中可能包含的“crib”的最多个数。
【输入格式】
第 1 行，1 个正整数 n，表示有 n 种“crib”。
接下来 n 行，每行一个字符串，表示 1 种“crib”。
最后 1 行，1 个字符串，表示密文。
【输出格式】
输出 1 个整数，表示密文中可能包含的“crib”的最大个数。
【输入样例 1】
2
WETTER
XORT
XEQFTWROEXGRES
【输出样例 1】
2
【输入样例 2】
2
CRYTIC
OVULIST
CCNDDZIYXDSMTOS
【输出样例 2】
2
【输入样例 3】
3
RUBRA
DOING
GRATED
XMQWVBJAMMRGCOXQPFIZOBMDUYOXJNGTTNRJOHLD
【输出样例 3】
8
【说明提示】
样例 1 说明：
如下安排两个 crib 的位置，最多包含 2 个 crib。
crib 也可能在如下两个位置，仍然是包含 2 个 crib。
样例 2 说明：
如下安排两个 crib 的位置，最多包含 2 个 crib。
【数据范围】
对 10%数据：n=1
另有 10%数据满足：所有“crib”的长度都等于 1。
对 100%数据：1≤n≤50；“crib”互不相同。“crib”的长度不超过 50，密文的长度不超过 105，输入中所有字符串只含大写英文字母。
参考答案
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
typedef long long LL;
const int MR=1e5+10;
bool check(const string &x,const string &y) {
if(x.size()!=y.size()) return false;
int l=x.size();
for (int i=0;i<l;i++) {
if(x[i]==y[i]) return false;
}
return true;
}
int n,dp[MR],cL[51];
string s,crib[51];
int main() {
cin>>n;
for (int i=1;i<=n;i++) {
cin>>crib[i];
cL[i]=crib[i].size();
}
cin>>s;
int len=s.size();
for (int i=1;i<=len;i++) {
dp[i]=dp[i-1];
for (int j=1;j<=n;j++) {
if(i>=cL[j] && check(s.substr(i-cL[j],cL[j]),crib[j])) {
dp[i]=max(dp[i-cL[j]]+1,dp[i]);
}
}
}
cout<<dp[len]<<endl;
return 0;
}