Page 1 of 2
671 - Spell checker
Posted: Mon Jul 28, 2003 3:04 pm
by anupam
here is my program for the problem 671 spell checker.
it gets rte.
but i can't understand.
plz elp.
thanks...
Code: Select all
thank you.
solved now.thanks again
[/b]
Posted: Thu Nov 13, 2003 11:44 pm
by UFP2161
N and M are switched in your declaration of the variable "a". This solves your RTE, but will give you a WA instead.
671 Spell Checker WA
Posted: Wed Jan 14, 2004 4:09 am
by Betty
Hey just wondering if I can get some help for this problem, I thought it was a nice and easy one, got the sample data/answer out correctly but seem to be getting a WA and I'm not sure why.
Code: Select all
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
char from[21], to[21];
int array[21][21];
void med(int f, int t) {
if(f<0 || t < 0) return;
med(f - 1, t);
for(int t1 = 0; t1 <= t; t1++) {
if( t1 == 0) {
array[f][t1] = f;
} else if (f == 0) {
array[f][t1] = t1;
} else {
int d = (t1-1 >= 0 && f-1 >=0)? array[f-1][t1-1] : -1;
int u = (t1-1 >= 0) ? array[f][t1-1] + 1 : -1;
int b = (f-1 >= 0) ? array[f-1][t1] + 1 : -1;
if(from[f-1] != to[t1-1]) {
d++;
}
int v = d;
if((u < v && u != 0) || v == -1) {
v = u;
}
if((b < v && b != 0) || v == -1) {
v = b;
}
array[f][t1] = v;
}
}
}
typedef vector<string> dictionary;
dictionary dict;
int main(){
char word[15];
while(1) {
scanf("%s", word);
if(strcmp("#",word) == 0) break;
dict.push_back(string(word));
}
while(1) {
scanf("%s", from);
if(strcmp(from, "#") == 0) break;
printf("%s", from);
if(find(dict.begin(), dict.end(), from) != dict.end()) {
printf(" is correct\n");
} else {
printf(":");
for(dictionary::iterator i = dict.begin(); i != dict.end(); i++) {
strncpy(to,(*i).c_str(),20);
med(strlen(from),strlen(to));
if(array[strlen(from)][strlen(to)] ==1)
printf(" %s", (*i).c_str());
}
printf("\n");
}
}
}
not the nicest code but I was adapting code from another problem I was working on (involving min ed distances too). If anyone sees a glaring error or has some sample data it would be nice to see.
Posted: Mon Jun 14, 2004 5:28 pm
by toomyem
Hey, I used different algorithm but also got WA. Have no idea what can be wrong. I tested a lot of different input data and for me it works. Don't know why I'm getting WA.
Posted: Mon Jun 14, 2004 5:38 pm
by UFP2161
Multiple Input.
Posted: Sun Aug 01, 2004 5:37 am
by Betty
UFP2161 wrote:Multiple Input.
anyone care to explain multiple input? i think i missed a couple of problems due to this one.
Posted: Wed Aug 04, 2004 3:15 pm
by Betty
Betty wrote:UFP2161 wrote:Multiple Input.
anyone care to explain multiple input? i think i missed a couple of problems due to this one.
nm i figured out multiple input, although i dont think i've re submitted this problem yet
Posted: Sat Jun 10, 2006 7:14 pm
by helloneo
Posted: Fri Oct 06, 2006 9:17 pm
by Mushfiqur Rahman
671wa...
Posted: Sat Aug 11, 2007 3:23 am
by lena
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char a[10000][19];
int n;
char b[40];
int comL(char * a,char *b)
{
int i = 0;
int res = 0;
while(a){if(a == b) res++;i ++;}
return res;
}
bool transform(char * a,char * b)
{
int x = strlen(a);
int y = strlen(b);
if(x>y) return transform(b,a);
int i,j;
int res = 0;
for(i=0;i<x;i++)
{
if(a!=b)
break;
res ++;
}
for(;a;i++)
{
if(a!=b[i+1])
break;
res++;
}
return res == x;
}
void solve()
{
int i;
for(i=0;i<n;i++)
if(strcmp(a,b) == 0)
{
printf("%s is correct\n",b);
return;
}
bool v = false;
printf("%s:",b);
int l = strlen(b);
for(i=0;i<n;i++)
{
if(strlen(a)==l)
{
if(comL(a,b) == l-1)
{
printf(" %s",a[i]);
}
}
else if(abs(strlen(a[i])-l)==1)
{
if(transform(a[i],b))
{
printf(" %s",a[i]);
}
}
}
printf("\n");
}
int main()
{
freopen("671.txt","r+",stdin);
//freopen("671_0.txt","w+",stdout);
int m;
scanf("%d",&m);
while( m -- )
{
n = 0;
while(gets(a[n]),strcmp(a[n],"#")!=0) n ++;
// getchar();
while(gets(b),strcmp(b,"#")!=0)
{
solve();
}
getchar();
if(m>0)printf("\n");
}
while(true){}
return 0;
}
Posted: Sat Aug 11, 2007 3:24 am
by lena
who can give me some input.
Posted: Sat Aug 11, 2007 10:43 pm
by Jan
Remove the following part.
And check your code for the following input set.
Input:
Code: Select all
1
hqghumeaylnlfd
fi
cvscxggbwkfn
#
hqghumeaylnlf
i
f
vscxggbwkfn
#
Code: Select all
hqghumeaylnlf: hqghumeaylnlfd
i: fi
f: fi
vscxggbwkfn: cvscxggbwkfn
Hope these help.
Posted: Sun Aug 12, 2007 9:42 am
by lena
while(true){} // is only for test use. ^o^.
I am doubt whether the string in the dictionary is empty or not. this will be important.
Posted: Sun Aug 12, 2007 11:27 am
by Jan
I think there are no empty strings in the dictionary.
Posted: Sun Aug 12, 2007 4:33 pm
by lena
if the two parts of input do not contain empty string. then my output is the same as yours.
