11048 - Automatic Correction of Misspellings
Moderator: Board moderators
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
11048 - Automatic Correction of Misspellings
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....
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.
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
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
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
11048 - Automatic Correction of Misspellings
I got 6 time Compile Error on this probs..
Some one pls help me find out the bug..
I know it is very hard.
Yet if some one favours me !!!!
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;
}
Yet if some one favours me !!!!
-
- Experienced poster
- Posts: 111
- Joined: Mon Jan 09, 2006 6:19 pm
- Location: Tehran, Iran
- Contact:
Thanks All
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.
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.
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
Re: Thanks All
Actually darko was right and it was the lack of #include <cstdio> that caused the compilation error. Good that you got AC, though.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.
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...
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
-
- Learning poster
- Posts: 56
- Joined: Tue Jun 13, 2006 5:18 pm
- Location: (CSE, SUST) Sylhet, Bangladesh
- Contact:
11048 - Automatic Correction of Misspellings
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........
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]
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.
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.