11048 - Automatic Correction of Misspellings

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

11048 - Automatic Correction of Misspellings

Post by jan_holmes » Sun Jul 23, 2006 7:10 pm

I have some questions about the problem statement :

1. The first rule states that "One letter is missing", how about if (letter is written elter) ???

2. The third rule states that "The order of two adjacent letters is wrong", how about (letter is written lteert) ???

thx....
Last edited by jan_holmes on Thu Jul 27, 2006 8:54 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Jul 23, 2006 7:16 pm

Two words are similar if we can transform one word into the other by doing exactly one of the misspellings listed above.
So, 'No' to both of your questions.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Jul 23, 2006 7:35 pm

ok... thx, mf... but could anyone give me sample input and output ????

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jul 24, 2006 12:38 am

Here are a few tests

Code: Select all

8
xletter
aletter
bletter
cletter
dletter
abcdefghijklmnoprstuvwxy
pq
x
24
aletter
aleter
blettter
cketter
dlettre
eletter
cletter
alette
letter
lette
laetter
abcdefghijklmnoprstuvwxz
zbcdefghijklmnoprstuvwxz
abcdegfhijklmnoprstuvwxy
x
y
p
q
xy
yx
xp
xq
xpq
xpy

Code: Select all

aletter is correct
aleter is a misspelling of aletter
blettter is a misspelling of bletter
cketter is a misspelling of cletter
dlettre is a misspelling of dletter
eletter is a misspelling of xletter
cletter is correct
alette is a misspelling of aletter
letter is a misspelling of xletter
lette is unknown
laetter is a misspelling of aletter
abcdefghijklmnoprstuvwxz is a misspelling of abcdefghijklmnoprstuvwxy
zbcdefghijklmnoprstuvwxz is unknown
abcdegfhijklmnoprstuvwxy is a misspelling of abcdefghijklmnoprstuvwxy
x is correct
y is a misspelling of x
p is a misspelling of pq
q is a misspelling of pq
xy is a misspelling of x
yx is a misspelling of x
xp is a misspelling of x
xq is a misspelling of pq
xpq is a misspelling of pq
xpy is unknown

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Mon Jul 24, 2006 11:41 am

AC now.... Thx mf... :D

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

11048 - Automatic Correction of Misspellings

Post by murkho » Mon Jul 24, 2006 7:18 pm

I got 6 time Compile Error on this probs..

Some one pls help me find out the bug..

Code: Select all


#include<iostream>
#include<string>
#include<stdlib.h>
#include<string.h>
#include<stdlib.h>

struct l{

			int length;
			int start;
			int idx;


		}list[26];



struct d{
			char word[26];
			int serial;

		}Dict[250001];


using namespace std;

char glo1[30],glo2[30];

int adjWrong(string s1,string s2);
int oneLetterWrong(string s1,string s2);
void convert(string s2);
int missing (char s1[], char s2[]);
void remove(char s[], int pos);





int main()
{
	int T,len,s,e,Q;
	int i,k;

	
	char t[30];

	char dict_word[30];
	int dict_index;

	int present,modified;

	//char tmp[30];
	string tmp;

	//freopen("auto.txt","r",stdin);

	for(i=1; i<= 25; i++)
	{
		list[i].start= (i-1) * 10000;
		list[i].length = i;
		list[i].idx = -1;	
	}


	
	scanf("%d",&T);

	for(i=0; i<T; i++)
	{
		cin>>tmp;
		
		len = tmp.length();
		list[len].idx++;
		s = list[len].start + list[len].idx;
		//strcpy(con,tmp);
		convert(tmp);
		strcpy(Dict[s].word,glo1);
		Dict[s].serial = i;
	
	}

	scanf("%d",&Q);

	for(i=0; i<Q; i++)
	{
		cin>>tmp;
		present = 0;
		modified = 0;
		
		dict_index = 20000;

		len = tmp.length();

		//Tesing whether in dict..of same lenght
		s = list[len].start;
		e = list[len].start + list[len].idx ;

		for(k=s; k<=e ; k++)
		{
			convert(tmp);
			if( strcmp(Dict[k].word ,glo1) ==0)
			{
				present = 1;
				break;
			}

			else if( adjWrong(Dict[k].word ,tmp) == 1)
			{
				//dj_wrong = true;			
				if(Dict[k].serial < dict_index)
				{
					strcpy(dict_word,Dict[k].word);
					dict_index = Dict[k].serial;
					modified = 1;					
					
				}
			}
			else if( oneLetterWrong(Dict[k].word ,tmp) == 1)
			{
				//adj_wrong = true;			
				if(Dict[k].serial < dict_index)
				{
					strcpy(dict_word,Dict[k].word);
					dict_index = Dict[k].serial;
					modified = 1;
					//break;
				}
			}



		
		}

		if(present == 1 )
		{
			cout<<tmp<<" is correct\n";
			continue;
		}
		
		//Testing whether one missing

		s = list[len+1].start ;
		e = list[len+1].start + list[len+1].idx ;


		for(k=s; k<=e && Dict[k].serial < dict_index; k++)
		{
			convert(tmp);
			strcpy(t,glo1);
			
			if(  missing(Dict[k].word , t ) == 1   )
			{
				if(Dict[k].serial < dict_index)
				{
					strcpy(dict_word,Dict[k].word);
					dict_index = Dict[k].serial;
					modified = 1;
					break;
				}

				
			
			
			}
			
		}

		
		// testing whether extra...
		s = list[len-1].start;
		e = list[len-1].start + list[len-1].idx;

		

		for(k=s; k<=e && Dict[k].serial < dict_index; k++)
		{
			convert(tmp);
			strcpy(t,glo1 );
			if(		missing( t, Dict[k].word) == 1		)
			{
				if(Dict[k].serial < dict_index)
				{
					strcpy(dict_word,Dict[k].word);
					dict_index = Dict[k].serial;
					modified = 1;
					break;
				}

			
			}
		
		}


		if(modified == 1)
			cout<<tmp<<" is a misspelling of "<<dict_word<<"\n";
		else
			cout<<tmp<<" is unknown\n";

	


	
	
	}





	return 0;
}

void  convert(string s2)
{

	//char tmp[30];
	int len = s2.length();
	int i;

	for(i=0; i<len; i++)
	{
		glo1[i] = s2[i];	
	}

	glo1[i] = NULL;

	return ;


}


int adjWrong(string s1,string s2)
{
	
	int len1,len2,count;
	int i;

	char ch1,ch2,pre1,pre2;

	len1 = s1.length();
	len2 = s2.length();

	if(len1 != len2) return -1;

	pre1 = s1[0];
	pre2 = s2[0];
	count = 0;

	for(i=1; i<len1; i++)
	{
		ch1 = s1[i];
		ch2 = s2[i];

		if(ch2 == pre1 && ch1 == pre2)
		{ count++;pre1 = ch1; pre2 = ch2;}

	}
	if(count == 1)
		return 1;	


	return -1;
}

int oneLetterWrong(string s1,string s2)
{


	int len1,len2;
	int i,val;
	len1 = s1.length();
	len2 = s2.length();
	val = 0;

	for(i=0; i<len1 || i<len2; i++)
	{
		if(i>len1)
			val++;
		else if(i>len2)
			val++;
		else if( s1[i] != s2[i])
			val++;

	
	}

	if(val == 1)
		return 1;
	else 
		return -1;
	

}

 void remove(char s[], int pos)
{

	int i,idx=-1,flg;
	int len = strlen(s);
	//char tmp[30];

	flg = 0;
	for(i=0; i<len; i++)
	{
		if(i!=pos )
			glo2[++idx] = s[i];
	}
	glo2[++idx] = NULL;

	return ;

	

}

int missing (char s1[], char s3[]) //s1 big s2 small
{

	int len1,i;
	len1 =strlen(s1);
	char tmp[30];
	for(i=0; i<len1; i++)
	{
		remove(s1,i);
		strcpy(tmp,glo2);
		if( strcmp(tmp,s3) ==0 )
		{
			return 1;		
		}	
	}

	return -1;


}
I know it is very hard.
Yet if some one favours me !!!!

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Mon Jul 24, 2006 9:07 pm

i think it is a better way to check your mailbox when you submit :wink:
In being unlucky I have the record.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Jul 24, 2006 9:25 pm

You have stdlib.h included twice, but not stdio.h. Maybe that's the reason?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jul 24, 2006 10:41 pm

Oh, and by the way, this is problem 11048, not 11054.

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

Thanks All

Post by murkho » Tue Jul 25, 2006 6:15 pm

Thanks For your reply..

Actually i think the problem is in Stl Library

The judge does not support some STL function.

How ever i changed All STL and Also the Algol i bit.

Now i got AC.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Re: Thanks All

Post by Krzysztof Duleba » Tue Jul 25, 2006 11:16 pm

murkho wrote: Actually i think the problem is in Stl Library

The judge does not support some STL function.

How ever i changed All STL and Also the Algol i bit.
Now i got AC.
Actually darko was right and it was the lack of #include <cstdio> that caused the compilation error. Good that you got AC, though.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Thu Jul 27, 2006 6:16 pm

oh yes, you're right.... this is problem number 11048, not 11054... my mistake... :oops:

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Jul 27, 2006 7:36 pm

You can edit the subject, you know... :)

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Thu Jul 27, 2006 8:55 pm

Yes, it is set now... :P

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

11048 - Automatic Correction of Misspellings

Post by Mushfiqur Rahman » Sat Aug 05, 2006 11:00 am

My code is getting WA for every time, but why? I tried to know it but i failed. I checked my code with many test cases(which has taken from board and made by me). But it's giving the correct answer.
Now I am giving my code. Anybody help please. I would be grateful to him forever........

Code: Select all

It has been removed after getting AC.
I know the first integer number "N" should not take in while loop, but i do that after getting many times WA. I think it's not a problem for getting WA. Because without doing this I also got WA.
Lastly thanks a million^million for you(Guru/ A great healper/ Experienced poster.
[/quote]
Last edited by Mushfiqur Rahman on Tue Aug 08, 2006 4:33 am, edited 1 time in total.

Post Reply

Return to “Volume 110 (11000-11099)”