671 - Spell checker

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

Moderator: Board moderators

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

671 - Spell checker

Post by anupam » Mon Jul 28, 2003 3:04 pm

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]
Last edited by anupam on Fri Nov 14, 2003 4:50 pm, edited 1 time in total.
"Everything should be made simple, but not always simpler"

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Thu Nov 13, 2003 11:44 pm

N and M are switched in your declaration of the variable "a". This solves your RTE, but will give you a WA instead.

Betty
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

671 Spell Checker WA

Post by Betty » Wed Jan 14, 2004 4:09 am

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.

toomyem
New poster
Posts: 6
Joined: Tue Jun 04, 2002 5:48 pm

Post by toomyem » Mon Jun 14, 2004 5:28 pm

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.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Mon Jun 14, 2004 5:38 pm

Multiple Input.

Betty
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

Post by Betty » Sun Aug 01, 2004 5:37 am

UFP2161 wrote:Multiple Input.
anyone care to explain multiple input? i think i missed a couple of problems due to this one.

Betty
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

Post by Betty » Wed Aug 04, 2004 3:15 pm

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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sat Jun 10, 2006 7:14 pm

never mind..;

Code: Select all

code removed
Last edited by helloneo on Thu Oct 12, 2006 3:57 am, edited 1 time in total.

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

Post by Mushfiqur Rahman » Fri Oct 06, 2006 9:17 pm

I got AC P.E but why? I tried to remove it for five times with all possibilities. Please anybody help.

Here is my code.

Code: Select all

Now I got AC
:o :o :o :o :o

lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

671wa...

Post by lena » Sat Aug 11, 2007 3:23 am

#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;
}

lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

Post by lena » Sat Aug 11, 2007 3:24 am

who can give me some input.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Aug 11, 2007 10:43 pm

Remove the following part.

Code: Select all

while(true){}
And check your code for the following input set.

Input:

Code: Select all

1

hqghumeaylnlfd
fi
cvscxggbwkfn
#
hqghumeaylnlf
i
f
vscxggbwkfn
#
Output:

Code: Select all

hqghumeaylnlf: hqghumeaylnlfd
i: fi
f: fi
vscxggbwkfn: cvscxggbwkfn
Hope these help.
Ami ekhono shopno dekhi...
HomePage

lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

Post by lena » Sun Aug 12, 2007 9:42 am

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.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Aug 12, 2007 11:27 am

I think there are no empty strings in the dictionary.
Ami ekhono shopno dekhi...
HomePage

lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

Post by lena » Sun Aug 12, 2007 4:33 pm

if the two parts of input do not contain empty string. then my output is the same as yours.
:cry:

Post Reply

Return to “Volume 6 (600-699)”