Codeforces 591B Rebranding

B. Rebranding

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

The name of one small but proud corporation consists of n lowercase English letters. The Corporation has decided to try rebranding — an active marketing strategy, that includes a set of measures to change either the brand (both for the company and the goods it produces) or its components: the name, the logo, the slogan. They decided to start with the name.

For this purpose the corporation has consecutively hired m designers. Once a company hires the i-th designer, he immediately contributes to the creation of a new corporation name as follows: he takes the newest version of the name and replaces all the letters xi by yi, and all the letters yi by xi. This results in the new version. It is possible that some of these letters do no occur in the string. It may also happen that xi coincides with yi. The version of the name received after the work of the last designer becomes the new name of the corporation.

Manager Arkady has recently got a job in this company, but is already soaked in the spirit of teamwork and is very worried about the success of the rebranding. Naturally, he can't wait to find out what is the new name the Corporation will receive.

Satisfy Arkady's curiosity and tell him the final version of the name.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the length of the initial name and the number of designers hired, respectively.

The second line consists of n lowercase English letters and represents the original name of the corporation.

Next m lines contain the descriptions of the designers' actions: the i-th of them contains two space-separated lowercase English letters xi and yi.

Output

Print the new name of the corporation.

Examples

Input

6 1
police
p m

Output

molice

Input

11 6
abacabadaba
a b
b c
a d
e g
f a
b b

Output

cdcbcdcfcdc

Note

In the second sample the name of the corporation consecutively changes as follows:

题目链接:http://codeforces.com/problemset/problem/591/B

这道题挺考思维的

详解:-1s1代表的本意abcdefg...0s1数组的下标和初始值0123456...1a-b1023456...2b-c1203456...3a-d3201456...4e-g3201654...5f-a5201634...6b-b5201634...7s1数组里面最终包含的值所对应的字符fcabgde...

 表二:

s2数组代表的本意

a

b

c

d

e

f

g

...

s2数组的下标

0

1

2

3

4

5

6

...

s2数组里面存的值

2

3

1

5

6

0

4

...

s2数组里面最终包含的值所对应的字符

c

d

b

f

g

a

e

...

 定义两个int类型数组来保存26个英文字母所表示的标号,可以开辟30个空间,s1[30] , s2[30]; 第一次交换ch1='a'与ch2='b' ,就交换s1数组里s1[ch1-'a']与s1[ch2-'a']的值,之后的1-6做一样的操作;

肯定会有疑问,为什么要交换s1[ch1-'a']与s1[ch2-'a']的值?交换过后是代表第-1行所表示的字符转换为第7行所表示的字符吗?

其实不是,如果你认为交换过后就是代表“第-1行所表示的字符转换为第7行所表示的字符”是错误的。

每次交换你可以看做   例如:表三:

-1

s1代表的本意

a

b

c

d

e

f

g

...

0

s1数组的下标和初始值

0

1

2

3

4

5

6

...

1

a-b

1

0

2

3

4

5

6

...

数组的值+'a'转换为相应的字符

b

a

c

d

e

f

g

...

其实交换过后代表

字符'a'是由字符'b'转化而来

字符'b'是由字符'a'转化而来

2

b-c

1

2

0

3

4

5

6

...

数组的值+'a'转换为相应的字符

b

c

a

d

e

f

g

...

字符'a'是由字符'b'转化而来

字符'b'是由字符'c'转化而来

字符'c'是由字符'a'转化而来

 你可以想想是不是这样的;这只是举了两个例子;

也就是说表四:

-1

s1代表的本意

a

b

c

d

e

f

g

......

s1数组的下标和初始值

0

1

2

3

4

5

6

......

7

s1数组里面最终包含的值所对应的字符

f

c

a

b

g

d

e

......

s1数组里面最终的值

5

2

0

1

6

3

4

结论

字符'a'是由字符'f'转化而来

字符'b'是由字符'c'转化而来

字符'c'是由字符'a'转化而来

字符'd'是由字符'b'转化而来

字符'e'是由字符'g'转化而来

字符'f'是由字符'd'转化而来

字符'g'是由字符'e'转化而来

......

推论

字符'f'最终转化为'a'

字符'c'最终转化为'b'

字符'a'最终转化为'c'

字符'd'最终转化为'b'

字符'g'最终转化为'e'

字符'd'最终转化为'f'

字符'e'最终转化为'g'

......

我们现在已经知道字符最终由哪个字符转化而来,也就是说我们得出的是,知道最终的字符,我们能找到它是由哪个最初的字符转换而来的,之后的怎么办呢? 我们需要转化为 题意给出了最初字符,能找到他最终要转换为哪个字符  这个就要好好思考一下怎么转换了!

其实定义两个数组,可以理解为,表四:  做这样的处理: 之后就变为表二: 

for(i=0; i<26; i++)
     s2[s1[i]]=i;

 为什么要这样处理呢?这样处理过后就会简化很多;再加上下面这个步骤,这道题就算是解决了;

1 for(i=0; i<n; i++)
2 {
3    str[i]=s2[str[i]-'a']+'a';
4 }

附上AC代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 2000010
 4 int main()
 5 {
 6     char str[N],ch1,ch2;
 7     int s1[30],s2[30];
 8     int n,m,i,x,y,t;
 9     while(scanf("%d%d",&n,&m)!=EOF)
10     {
11         scanf("%s",str);
12         for(i=0;i<26;i++)
13             s1[i]=i;
14         for(i=0;i<m;i++)
15         {
16             scanf(" %c %c", &ch1, &ch2);
17             x=ch1-'a';
18             y=ch2-'a';
19             t=s1[x];
20             s1[x]=s1[y];
21             s1[y]=t;
22         }
23         for(i=0;i<26;i++)
24             s2[s1[i]]=i;
25         for(i=0;i<n;i++)
26         {
27             str[i]=s2[str[i]-'a']+'a';
28         }
29         printf("%s\n",str);
30     }
31     return 0;
32 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Jerry的SAP技术分享

聊聊JavaScript和Scala的表达式 Expression

函数f的实现,会检查这两个参数的类型,如果是函数,则执行函数调用,再打印其返回值,否则直接打印传入的表达式的值。

8920
来自专栏浪淘沙

实训day04--二维数组,面向对象

2018.06.07 1.方法的签名 cn.edu360.function.Demo1.add(int ,int)

10930
来自专栏Vamei实验室

Python基础07 函数

函数最重要的目的是方便我们重复使用相同的一段程序。 将一些操作隶属于一个函数,以后你想实现相同的操作的时候,只用调用函数名就可以,而不需要重复敲所有的语句。 函...

20990
来自专栏数据结构与算法

16:忽略大小写的字符串比较

16:忽略大小写的字符串比较 总时间限制: 1000ms 内存限制: 65536kB描述 一般我们用strcmp可比较两个字符串的大小,比较方法为对两个字符串...

39390
来自专栏androidBlog

java 正则表达式浅析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

8310
来自专栏程序员互动联盟

【编程基础】Java初始化有何玄机?

对于Java的初始化顺序大家应该清楚,之前在网站上面有专门的讲解,大家可以通过文章下面的“查看原文”来阅读。 初始化顺序总结起来就是: 1、无继承情况的初始化顺...

37190
来自专栏Laoqi's Linux运维专列

python3–元祖+列表+字典

32840
来自专栏猿人谷

数组与指针

一、数组        数组是由类型名、标识符和维数组成的复合数据类型,类型名规定了存放在数组中的元素类型,维数则指定数组中包含的元素个数。        数组...

21580
来自专栏JavaEE

redis学习之redis基本数据类型前言:数据类型详解:

11530
来自专栏Python小屋

Python中表达式int(&#39;0x10, 36)的值是。。。

在Python中,int()可用来把实数转换为整数,或者把数字字符串按指定进制转换为十进制数,详见文末的相关阅读。 然而,下面的代码又应该如何解释呢? >>> ...

30860

扫码关注云+社区

领取腾讯云代金券