11048 - Automatic Correction of Misspellings

[jan_holmes]

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....

[mf]

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]

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

[mf]

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]

AC now.... Thx mf...

[murkho]

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 !!!!

[arsalan_mousavian]

i think it is a better way to check your mailbox when you submit

[Darko]

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

[mf]

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

[murkho]

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.

[Krzysztof Duleba]

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.

[jan_holmes]

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

[Darko]

You can edit the subject, you know...

[jan_holmes]

Yes, it is set now...

[Mushfiqur Rahman]

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]