C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1095 Anigram单词

题目

一个单词a如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的Anigram,例如单词army和mary互为Anigram。另:相同的2个单词不算Anigram。现在给定一个字典,输入Q个单词,从给出的字典中找出这些单词的Anigram。

思路

一个map保存原串出现次数,一个map保存排序串出现次数,减一下

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
int n,q;
char s[20],sp[20];
map<string,int>mp1;
map<string,int>mp2;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
strcpy(sp,s);
sort(sp,sp+strlen(sp));
mp1[s]++;//cout<<s<<';'<<mp[s]<<endl;
mp2[sp]++;
}
cin>>q;
for(int i=1;i<=q;i++){
cin>>s;
strcpy(sp,s);
sort(sp,sp+strlen(sp));
//cout<<sp<<':'<<mp[sp]<<' '<<s<<':'<<mp[s]<<' ';
cout<<mp2[sp]-mp1[s]<<endl;
}
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/23609/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!