Algorithm1.1 字符串-map匹配
[TOC]
字符串映射
利用map进行字串匹配、替换
https://www.luogu.com.cn/problem/P1603
题目大意：给六个字符串，然后如果有映射的进行映射为数字，没有的就不映射。输出最后映射完的结果
1、准备数据结构：用于匹配的map字典=>将字符串与数字进行映射
2、易错：第一位随便匹配，后面的位数如果是1位的话，拼接到一起之前要补0，例如如果是5，要输出05。
声明字符串映射的数据结构map
// 声明map
map<string, int> mp;
// 进行映射
mp["one"] = 1; mp["two"] = 2; /* ……*/ mp["nineteen"] = 19; mp["twenty"] = 20; mp["one"] = 1;
进行匹配：
int main() {
for (int i = 0; i < 6; ++i) {
cin>>str;
if (mp[str]){
int cnt = mp[str]*mp[str]%100;
if (!cnt) continue;
ans[idx++] = cnt;
}
}
sort(ans, ans+idx);
printf("%d", ans[0]);
for (int i = 1; i < idx; ++i) {
if (ans[i] < 10) printf("0");
printf("%d", ans[i]);
}
return 0;
}
两个map进行正向反向映射
https://www.luogu.com.cn/problem/P1071
题目大意：对已有的编码规则进行分析，根据题目给的两个规则看是否正确；正确的话把题目给的原字串再进行编码，输出。
1、解码译码类问题，用两个map进行正向反向映射，方便做题
2、判断规则方面，看看有没有一个映射多个的话，可以利用map的count(key)函数，对于传进来的key进行判断是否已经出现过，出现过=>会返回1，没有出现过返回0。
然后再判断已有的mp[key] ?= newvalue来判断是否存在同一个key有不同的映射。
#include <iostream>
using namespace std;
#include <map>
map<char, char> mp, rvmp;
#define maxn 105
char origin[maxn], after[maxn], target[maxn];
int vis[maxn];
#include <string.h>
int main() {
scanf("%s%s%s", origin, after, target);
// 判断第一个规则
for (int i = 0; i < strlen(origin); ++i) {
// 已经有了，并且和当前又映射的不一样 => 又重复的
if ((mp.count(origin[i]) && mp[origin[i]] != after[i]) || (rvmp.count(after[i]) && rvmp[after[i]] != origin[i])) {printf("Failed\n"); return 0;}
mp[origin[i]] = after[i];
rvmp[after[i]] = origin[i];
}
// 判断第二个规则
char tmp = 'A';
for (int i = 0; i < 26; ++i) if (!rvmp.count(tmp+i)) {printf("Failed"); return 0;}
// 输出
for (int i = 0; i < strlen(target); ++i) if (target[i] != ' ') printf("%c", mp[target[i]]);
return 0;
}
尾部匹配
https://www.luogu.com.cn/problem/P3955
两个思路：
- 利用string 字符串匹配
- 利用数字看相等，利用数字的话通过取模截取有效部分
利用取模截取有用部分的方法：
#include <iostream>
using namespace std;
const int maxn = 1e3+9;
int s[maxn], n, q, sq, l, mod[11] = {0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
#include <algorithm>
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) scanf("%d", s+i);
sort(s+1, s+1+n);
for (int i = 1; i <= q; ++i) {
scanf("%d%d", &l, &sq);
int fd = 0;
for (int j = 1; j <= n; ++j) if (s[j]%mod[l] == sq) {fd = 1; cout<<s[j]<<endl; break;}
if (fd) continue;
else puts("-1");
}
return 0;
}