The comments below refer to the problem named "Help!" (number 10728).
You can search the web for "Unification" to get a full description of an algorithm to solve this problem. (Actually, full unification works on trees not just strings, and if finds the "most general unifier" which transforms the patterns into a common pattern such that a string matches the unified pattern if and only if it matches both the original patterns.)
Here are some hints:
- as shown in the example, the two pattern matching problems are independent, so you should rename the variables in one pattern so that they are different from the variables in the other
- compare the two patterns a word at a time (any order, left-to-right will do)
- whenever a variable must match a word, replace all instances of the variable by the word in both patterns
- whenever a variable must match a variable, replace one by the other (doesn't matter which)
- whenever two words must match, if they're equal, fine; otherwise the match is impossible
Last edited by gvcormac on Sun Oct 10, 2004 7:01 pm, edited 1 time in total.
I will explaine it using matrix,but you will see that you can solve it just using 2 arrays.Let take a matrix a[n,n].a[i,j] means how many moves we must do for making word S polindrom(were S is our word without last j characters and without first i caracters).Our answer will be a[0,0].
You must find elements of half of this matrixt(this matrix is simetrically)
diagonally.
a[i,i]=0 for all 0<=i<=n.
Now if we want to find element a[i,j] for word s[1..n] then
1. If s[i+1]=s[n-j] then a[i,j]=a[i+1,j+1]
2. if s<>s[j] then a[i,j]=min(a[i,j+1],a[i+1,j],a[i+1,j+1])+1
For example let take word s='abccda'(n=6) at first we have matrix a[n,n].
We must find elements of green ones.
At fisrt we must start finding them in this way(a[0,n-1] a[1,n-2] a[2,n-3]..)
for finding a[0,5] we must see if s[0+1]=s[1]='a' is equal to s[6-5]=s[1]='a' than a[0,5]=a[1,6]=0(Its not hard to see that a[i,n-i-1]=0 for all 0<=i<n.
Now for a[0,4].S[1]='a' s[6-4]=s[2]='b' than a[0,4]=min(a[1,4],a[0,5],a[1,5])+1 a[0,4]=1. Then we must find a[1,3] then a[2,2] then a[3,1] then a[4,0] then a[0,3] then a[1,2] and so on.And you will get a[0,0](for this test case a[0,0]=1).
This is all.
thanks...
i think your solution is hm... very intresting but i solved this task using sth. like greedy... but once again thanks for your answere becouse thanks to that i will learn sth. morwe
Hi Eduard, can you explain me why I get WA for this problem.
I can't find the mistake
Here is my code
[pascal]var i,j,k,l,n,m,p,r,t:integer;
a:array[1..1001,0..1001] of integer;
c:char;
s:array[1..1001] of char;
function min(a,b,c:integer):integer;
var m:integer;
begin
if a<b then m:=a else m:=b;
if c<m then m:=c;
min:=m;
end;
begin
readln(t);
fillchar(a,sizeof(a),0);
for r:=1 to t do
begin
read(c);
i:=0;
while c in ['a'..'z'] do
begin
inc(i);
s:=c;
read(c);
end;
read(c);
n:=i;
for j:=2 to n do
for i:=1 to n-j+1 do
if s=s[i+j-1] then a[i,j]:=a[i+1,j-2] else
a[i,j]:=1+min(a[i+1,j-2],a[i,j-1],a[i+1,j-1]);
writeln('Case ',r,': ',a[1,n]);
end;
end.
[/pascal]
At first you are using to much memory.And you are reading not right.
this code is getting AC.
[pascal]
var i,j,k,l,n,m,p,r,t:integer;
a:array[1..1001,0..1001] of integer;
c:char;
s:array[1..1001] of char;
function min(a,b,c:integer):integer;
var m:integer;
begin
if a<b then m:=a else m:=b;
if c<m then m:=c;
min:=m;
end;
begin
readln(t);
fillchar(a,sizeof(a),0);
for r:=1 to t do
begin
read(c);
i:=0;
while c in ['a'..'z'] do
begin
inc(i);
s:=c;
if eoln then break; <----------This line you need
read(c);
end;
readln; <----------And this(not read(c))
n:=i;
for j:=2 to n do
for i:=1 to n-j+1 do
if s=s[i+j-1] then a[i,j]:=a[i+1,j-2] else
a[i,j]:=1+min(a[i+1,j-2],a[i,j-1],a[i+1,j-1]);
writeln('Case ',r,': ',a[1,n]);
end;
end. [/pascal]