OJ Board

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

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;


}

Code: Select all

It has been removed after getting AC.