首页 > 代码库 > uva 1509 - Leet(暴力)
uva 1509 - Leet(暴力)
题目链接:uva 1509 - Leet
题目大意:给出k,表示一个字符可以对应k给字符编码,给出字符串1,问时候有符合的编码可以生成字符串2.
解题思路:暴力枚举,对于每个碰到的字符记录对应的编码。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 105;
const int maxc = 200;
int k, len1, len2, rec[maxc][3];
char str1[maxn], str2[maxn];
bool check (int l, int r, int pos) {
for (int i = 0; i + l <= r; i++) {
if (str2[l+i] != str2[pos+i])
return false;
}
return true;
}
bool dfs (int pos1, int pos2) {
if (pos1 == len1)
return pos2 == len2;
if (pos2 == len2)
return false;
char ch = str1[pos1];
if (rec[ch][0] == -1) {
rec[ch][0] = pos2;
for (int i = 1; i <= k; i++) {
rec[ch][1] = pos2+i-1;
if (dfs(pos1+1, pos2 + i))
return true;
}
rec[ch][0] = -1;
} else {
if (!check(rec[ch][0], rec[ch][1], pos2))
return false;
if (dfs(pos1+1, pos2 + rec[ch][1] - rec[ch][0] + 1))
return true;
}
return false;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%d%s%s", &k, str1, str2);
memset(rec, -1, sizeof(rec));
len1 = strlen(str1);
len2 = strlen(str2);
printf("%d\n", dfs(0,0) ? 1 : 0);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。