CF 254C(易位构字法）

Posted on by
内容目录
C. 易位构字法
time limit per test

1 second

memory limit per test

256 megabytes

input

input.txt

output

output.txt

异位构字就是把一个字符串的顺序改变，可以得到另一个字符串.

对字符串 s 和 t ,至少修改 s 多少位，能使 s 和 t 易位构字？如果有很多方法，输出 s 易位后字典序最小的。

Input

两行 s, t. 长度不超过 105 ，只有大写字母。

Output

第一行输出最小修改次数，第二行输出 s 修改后字典序最小的字符串。

Sample test(s)
input
ABA
CBA
output
1
ABC
input
CDBABC
ADCABD
output
2
ADBADC
Note

 第二个数据，s 可改成: "ADBADC", "ADDABC",
"CDAABD", "CDBAAD", "CDBADA",
"CDDABA", "DDAABC", "DDBAAC".
字典序最小的是 "ADBADC".

直接处理字符串。

program word;
const
   maxn=100000;
var
   s,t:ansistring;//->ansistring
   n,i,j,ans,size,head:longint;
   pass,a1,a2,deln:array['A'..'Z'] of longint;
   add:array[1..26] of char;
   addn:array[1..26] of longint;
   ic:char;
begin
   assign(input,'input.txt');
   assign(output,'output.txt');
   reset(input);
   rewrite(output);
   fillchar(a1,sizeof(a1),0);
   fillchar(a2,sizeof(a2),0);
   fillchar(pass,sizeof(pass),0);
   fillchar(deln,sizeof(deln),0);
   readln(s);
   readln(t);
   n:=length(s);
   for i:=1 to n do inc(a1[s[i]]);
   for i:=1 to n do inc(a2[t[i]]);

   size:=0;
   ans:=0;
   for ic:='A' to 'Z' do
      if a2[ic]>a1[ic] then
      begin
         inc(size);
         add[size]:=ic;
         addn[size]:=a2[ic]-a1[ic];
         inc(ans,addn[size]);
      end
      else if a2[ic]<a1[ic] then
      begin
         deln[ic]:=a1[ic]-a2[ic];
      end;

   writeln(ans);
   head:=1;
   for i:=1 to n do
   begin
      inc(pass[s[i]]);
      if deln[s[i]]>0 then
      begin
         if (add[head]<s[i]) or (deln[s[i]]>a1[s[i]]-pass[s[i]]) then
         begin
            dec(deln[s[i]]);
            s[i]:=add[head];
            dec(addn[head]);
            if addn[head]=0 then inc(head);
         end;
      end;
   end;
   writeln(s);
   close(input);
   close(output);
end.