123 - Searching Quickly

[FlyDeath]

My program can handle output with spaces between words.But I still always get WA.I really don't knwo why.Can someone tell me?

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char iword[50][11];
char title[200][15][101];
char mixtitle[200][201];
char print[1000][101];
int titleword[200];
int howiword=0;
int howtitle=0;
int howprint=0;

int prestrcmp(char *a,char *b)
{
	int i,j;
	int p;
	int t1,t2;
	int result=0;
	int flag=0;
	int flag1=0;
	char m1[101],m2[101];
	p=0;
	for(i=0;i<101;i++)
	{
		m1[i]=0;
		m2[i]=0;
	}
	for(i=0;i<strlen(a);i++)
	{
		if(a[i]>=65&&a[i]<=90)
		{
			m1[p]=a[i];
			p++;
		}
	}
	p=0;
	for(i=0;i<strlen(b);i++)
	{
		if(b[i]>=65&&b[i]<=90)
		{
			m2[p]=b[i];
			p++;
		}
	}
	result=strcmp(m1,m2);
	if(result!=0)
		return result;
	else
	{
		for(i=0;i<howtitle;i++)
		{
			if(strlen(a)==strlen(mixtitle[i]))
			{
				flag=0;
				for(j=0;j<strlen(a);j++)
				{
					if(labs(a[j]-mixtitle[i][j])!=0&&labs(a[j]-mixtitle[i][j])!=32)
					{
						flag=1;
						break;
					}
				}
				if(flag==0)
					t1=i;
				break;
			}
		}
		for(i=0;i<howtitle;i++)
		{
			if(strlen(b)==strlen(mixtitle[i]))
			{
				flag=0;
				for(j=0;j<strlen(b);j++)
				{
					if(labs(b[j]-mixtitle[i][j])!=0&&labs(b[j]-mixtitle[i][j])!=32)
					{
						flag=1;
						break;
					}
				}
				if(flag==0)
					t2=i;
				break;
			}
		}
		if(t1!=t2)
			return t1-t2;
		else
		{
			t1=0;
			t2=0;
			for(i=0;i<strlen(a);i++)
			{
				if(a[i]>=65&&a[i]<=90)
				{
					t1=i;
					break;
				}
			}
			for(i=0;i<strlen(b);i++)
			{
				if(b[i]>=65&&b[i]<=90)
				{
					t2=i;
					break;
				}
			}
			return t1-t2;
		}
	}
}

int sort(const void *a,const void *b)
{
	return prestrcmp((char *)a,(char *)b);
}

void main()
{
	int temp2=0;
	char temp;
	int result=0;
	int yesno=0;
	int ptr;
	int i=0,j=0,k=0,m=0,n=0;
	int flag;
	int flag1;
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	for(i=0;i<50;i++)
		for(j=0;j<11;j++)
			iword[i][j]=0;
	for(i=0;i<200;i++)
	{
		for(j=0;j<201;j++)
			mixtitle[i][j]=0;
		for(j=0;j<15;j++)
			for(k=0;k<101;k++)
				title[i][j][k]=0;
		titleword[i]=0;
	}
	for(i=0;i<1000;i++)
		for(j=0;j<101;j++)
			print[i][j]=0;
	while(1)
	{
		scanf("%s",&iword[howiword]);
		howiword++;
		if(strcmp(iword[howiword-1],"::")==0)
		{
			howiword--;
			break;
		}
	}
	ptr=0;
	howtitle=0;
	fgets(mixtitle[howtitle],200,stdin);
	while(1)
	{
		if(fgets(mixtitle[howtitle],200,stdin)==NULL)
			break;
		if(mixtitle[howtitle][strlen(mixtitle[howtitle])-1]=='n')
			mixtitle[howtitle][strlen(mixtitle[howtitle])-1]=0;
		ptr=0;
		for(i=0;i<strlen(mixtitle[howtitle]);i++)
		{
			if(mixtitle[howtitle][i]>=65&&mixtitle[howtitle][i]<=90)
			{
				title[howtitle][titleword[howtitle]][ptr]=mixtitle[howtitle][i]+32;
				ptr++;
			}
			else if(mixtitle[howtitle][i]>=97&&mixtitle[howtitle][i]<=122)
			{
				title[howtitle][titleword[howtitle]][ptr]=mixtitle[howtitle][i];
				ptr++;
			}
			else if(mixtitle[howtitle][i]==' ')
			{
				if(strcmp(title[howtitle][titleword[howtitle]],"")!=0)
				{
					title[howtitle][titleword[howtitle]][ptr]=0;
					titleword[howtitle]++;
					ptr=0;
				}
			}
			else if(mixtitle[howtitle][i]==0)
			{
				if(strcmp(title[howtitle][titleword[howtitle]],"")!=0)
				{
					title[howtitle][titleword[howtitle]][ptr]=0;
					titleword[howtitle]++;
					ptr=0;
				}
				break;
			}
		}
		if(strcmp(title[howtitle][titleword[howtitle]],"")!=0)
		{
			title[howtitle][titleword[howtitle]][ptr]=0;
			titleword[howtitle]++;
			ptr=0;
		}
		howtitle++;
	}
	for(i=0;i<howtitle;i++)
		for(j=0;j<strlen(mixtitle[i]);j++)
			if(mixtitle[i][j]>=65&&mixtitle[i][j]<=90)
				mixtitle[i][j]=mixtitle[i][j]+32;
	for(i=0;i<howtitle;i++)
	{
		for(j=0;j<titleword[i];j++)
		{
			result=0;
			yesno=0;
			for(k=0;k<howiword;k++)
			{
				if(strcmp(iword[k],title[i][j])==0)
					result=1;
			}
			if(result==0)
				yesno=1;
			if(yesno==1)
			{
				flag=0;
				flag1=0;
				strcpy(print[howprint],mixtitle[i]);
				for(k=0;k<strlen(mixtitle[i]);k++)
				{
					if(print[howprint][k]>=97&&print[howprint][k]<=122)
					{
						if(flag1==0)
						{
							flag++;
							flag1=1;
						}
					}
					else if(print[howprint][k]==' ')
						flag1=0;
					if(flag-1==j&&flag1==1)
						print[howprint][k]=print[howprint][k]-32;
				}
				howprint++;
			}
		}
	}
	qsort(print,howprint,sizeof(char)*101,sort);
	for(i=0;i<howprint;i++)
		printf("%sn",print[i]);
}

[C8H10N4O2]

Does anyone know of any special cases? My code works for the example case but gives me WA.
[cpp]
#pragma warning (disable:4786)
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cctype>
#include <cstring>

using namespace std;

void main()
{
char B[1000],*P;
int i,j,k,N;
bool Duplicate;
vector<string> Ignore;
vector<string> Titles;
map<string,vector<int> > Index;
map<string,vector<int> >::iterator Idx;
string Title,Word,UWord;

do
{
scanf("%s",B);
for(i=0;i<strlen(B);i++)
{
B=tolower(B);
}
Ignore.push_back(B);
}
while(strcmp(B,"::")!=0);
Ignore.pop_back();

scanf("\n");
N=0;
while(fgets(B,1000,stdin)!=NULL)
{
for(i=0;i<strlen(B);i++)
{
B=tolower(B);
}
P=strchr(B,'\n');
if(P)
*P='\0';
Titles.push_back(B);

Title="";
P=strtok(B," ");
Duplicate=false;
while(P)
{
if(find(Ignore.begin(),Ignore.end(),P)==Ignore.end())
{
if(Title=="")
{
Title+=P;
}
else
{
Title+=" ";
Title+=P;
}
if(find(Index[P].begin(),Index[P].end(),N)==Index[P].end())
{
Index[P].push_back(N);
}
}

P=strtok(NULL," ");
}
N++;
}

for(Idx=Index.begin();Idx!=Index.end();Idx++)
{
for(i=0;i<(*Idx).second.size();i++)
{
k=-1;
Word=(*Idx).first;
UWord=Word;
Title=Titles[(*Idx).second];
for(j=0;j<Word.size();j++)
{
UWord[j]=toupper(UWord[j]);
}
while(true)
{
k=Title.find(Word,k+1);
if(k!=string::npos)
{
printf("%s",Title.substr(0,k).c_str());
printf("%s",UWord.c_str());
printf("%s\n",Title.substr(k+Word.size(),Title.size()-k-Word.size()).c_str());
}
else
{
break;
}
}
}
}
}[/cpp]

[bodq]

Does anyone know of any special cases? My code works for the example case but gives me WA.

I guess I'll spoil you the fun if I'd tell you what exactly is wrong, so here is just the test case:

foo
::
o a foozoobar

have a nice day!

[C8H10N4O2]

Thanks, I will look into it:)

[Rossi]

runtime error?????

[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>

typedef struct{
int len;
char *main;
}TITLE;

int compstr(const void *a,const void *b)
{return strcmp((char *)a,(char *)b);}

int compptr(const void *a,const void *b)
{return strcmp(*(char **)a,*(char **)b);}

void print(char *,char *);
void strlower(char *);
int searchkey(char *);
char *instr(char *,char *);

int knum;
char keys[52][16];

int main(void)
{
register int i,j;
int tnum,rnum;
char str[16384],*p;
char *arr[3200];
TITLE ttl[210];

for(knum=0;;knum++){
gets(str);
p=strtok(str," \t");
strcpy(keys[knum],p);
if(strcmp(keys[knum],"::")==0)
break;
strlower(keys[knum]);
}

qsort((void *)keys,knum,sizeof(keys[0]),compstr);

for(tnum=rnum=0;;tnum++){
if(gets(str)==NULL)
break;

ttl[tnum].len=strlen(str);
ttl[tnum].main=new char[ttl[tnum].len+1];
strlower(str);
strcpy(ttl[tnum].main,str);

p=strtok(str," \t");
for(;p;){
if(searchkey(p)==0){
arr[rnum]=new char[strlen(p)+1];
strcpy(arr[rnum],p);
rnum++;
}
p=strtok(NULL," \t");
}
}

qsort((void *)arr,rnum,sizeof(char *),compptr);

for(i=0;i<rnum;i++){
for(j=0;j<tnum;j++){
if((p=instr(ttl[j].main,arr))!=NULL){
print(ttl[j].main,p);
break;
}
}
}

for(i=0;i<tnum;i++)
delete []ttl.main;

for(i=0;i<rnum;i++)
delete []arr;

return 0;
}

void strlower(char *str)
{
while(*str){
*str=tolower(*str);
str++;
}
}

int searchkey(char *key)
{
int res,left,right,mid;

left=0;
right=knum-1;
while(left<=right){
mid=(left+right)/2;
res=strcmp(key,keys[mid]);
if(res<0)
right=mid-1;
else if(res>0)
left=mid+1;
else
return 1;
}
return 0;
}

void print(char *in,char *p)
{
strlower(in);
while(!isspace(*p)){
*p=toupper(*p);
p++;
}
printf("%s\n",in);
}

char *instr(char *src,char *sub)
{
register int i,j;
int lsrc,lsub;

lsrc=strlen(src);
lsub=strlen(sub);

for(i=0;i<lsrc;i++){
if((i==0||isspace(src[i-1]))&&src==sub[0]){
for(j=1;j<lsub;j++){
if(src[j+i]!=sub[j])
break;
}
if(j==lsub&&(src[j+i]==NULL||isspace(src[j+i]))){
return ((char *)&src);
}
}
}

return NULL;
}[/cpp]

[C8H10N4O2]

The runtime error is probably due to the gratuitous use of pointers... Try running through it with a debugger. There is probably an indexOutOfBounds exception somewhere.

[Archangel]

Here is my algorithm:

Code: Select all

          0.three array: ignore,title,keyword(also store "the title it come from"and                                  "keyword position in the title").
          1.Read in words to ignore and stored them in a array(ignore).
          2.Read in titles, one word at a time to a string.(If read in a upper
             case letter, it will be changed to lower case and store to the  
             string).
          3.compare the string with the ignore word's array to check if it is an ignore or not. 
          4.If it's not a ignore word, copy the string to the keyword array and
             title array;if it's a ignore word, just copy the string to the title array.
          5.use bubble sort to sort the keyword array.
          6.print the result character by character using keyword array.

Anybody can give me a suggestion to improve my program? I got Time Limit Exceeded!

[PMNOX]

you shouldn't use arrays, rb-trees are much faster.
And you should use quicksort instead of bubble sort .

[Archangel]

Thanks for your great help!

[PMNOX]

to solve this problem I used stl (set), if you don't know it i can sent you a tutorial

[route]

how to determine the number of lines for one set of input? how to code for the inputs ?

[yiuyuho]

There is only one set of input

What do you mean how to code?

[route]

I mean.... for a normal question....
Input:
1 <--- 1st set of input
2 <----2nd set of input

We can code:
If it is not the end-of-file
read one set of input for one line.

But for problem 123, we cannot determine the lines for one set of inputs,

Input:
XXXX -
XXXX |-- how many lines ?
XXXX -

[yiuyuho]

All Title and key word is only on one line, I think

[minskcity]

Can anybody test my code or give me test cases that are likely to result in WA with my code.

Or find any mistakes in my code.

My algorithm description:

1:Read titles, creating an array of indexing words at the same time.
2:Sort the array of indexing words.
3:Take indexing words one by one from sorted array, look for that word in titles, print a string of answer when found.

My code ( )
[cpp]#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>

char buffer[300];
char ignore[50][20];
char index[500][100];
int ignore_num;
int index_num;

struct my_title{
char word[15][100];
int word_num;
};

my_title title[200];

int same(char in1[100], char in2[100]){
for(int i = 0; i < 100; i++){
if(in1 != in2) return 0;
if((in1 == 0) && (in2 == 0)) return 1;
}
return 1;
}

int in_ignore(char in[100]){
for(int i = 0; i < ignore_num; i++)
if(same(in,ignore)) return 1;
return 0;
}

int in_index(char in[100]){
for(int i = 0; i < index_num; i++)
if(same(in,index)) return 1;
return 0;
}

int fcmp(const void *in1,const void *in2){
for(int i = 0; i < 100; i++){
if(((char *)in1) < ((char *)in2)) return -1;
if(((char *)in1) > ((char *)in2)) return 1;
if(!((char *)in1)[i]) return 0;
}
return 0;
}

void print_as_answer(int tn, int ind){
int j;
for(int i = 0; i < title[tn].word_num; i++){
if(ind == i){
for(j = 0; title[tn].word[i][j]; j++)
cout << char(title[tn].word[i][j] - 32);
} else cout << title[tn].word[i];
if(i != title[tn].word_num) cout << " ";
}
cout << "\n";
}

int main(){
ignore_num = 0;
index_num = 0;
cin >> ignore[ignore_num];
while(ignore[ignore_num][0] != ':'){
ignore_num++;
cin >> ignore[ignore_num];
}

int title_num = 0;
int kk = 0;
int bk;
while(gets(buffer)){
if(!buffer[0]) break;
for(int i = 0; buffer[i]; i++)
if(isalpha(buffer[i]))
if(!islower(buffer[i])) buffer[i] += 32;
bk = 0;
while(1){
if(buffer[bk] == ' '){
title[title_num].word[title[title_num].word_num][kk] = 0;
if(!in_ignore(title[title_num].word[title[title_num].word_num]))
if(!in_index(title[title_num].word[title[title_num].word_num])){
for(int i = 0; i <= kk; i++)
index[index_num][i] = title[title_num].word[title[title_num].word_num][i];
index_num++;
}
title[title_num].word_num++;
kk = 0;
bk++;
continue;
}
if(!buffer[bk]){
title[title_num].word[title[title_num].word_num][kk] = 0;
if(!in_ignore(title[title_num].word[title[title_num].word_num]))
if(!in_index(title[title_num].word[title[title_num].word_num])){
for(int i = 0; i <= kk; i++)
index[index_num][i] = title[title_num].word[title[title_num].word_num][i];
index_num++;
}
title[title_num].word_num++;
kk = 0;
break;
}
title[title_num].word[title[title_num].word_num][kk] = buffer[bk];
kk++;
bk++;
}
title_num++;
}

qsort(&index,index_num,100,&fcmp);

for(int i = 0; i < index_num; i++)
for(int j = 0; j < title_num; j++)
for(int k = 0; k < title[j].word_num; k++)
if(same(index[i],title[j].word[k]))
print_as_answer(j,k);

getch();
return 0;
}[/cpp]
I know it's too long.