10100 - Longest Match

[Choi]

I try to submit , But Wa...

I don't know why get WA...Help Me T_T

Code: Select all

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

#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define N 1000
int LCS[N+1][N+1];

main()
{
    char s1[N+1][1001], s2[N+1][1001];
    char tmp[1001], tmp1[1001];
    int i, j,j1, j2;
    int n, m;
    char *p;
    int count = 1;
    int c1, c2;
    while(fgets(tmp, 1001, stdin)!=NULL)
    {

        fgets(tmp1, 1001, stdin);

        c1 = c2 = m = n = 0;
        memset(LCS, 0, sizeof(LCS));

        j1 = strlen(tmp)-1; j2 = strlen(tmp1)-1;
        tmp[j1]='\0';       tmp1[j2] = '\0';

        for(i = 0; i < j1; i++)
        {
            if(isspace(tmp[i]))
                c1++;
            if(!isalnum(tmp[i]))
                tmp[i] = ' ';
        }
        for(i = 0; i < j2; i++)
        {
            if(isspace(tmp1[i]))
                c2++;
            if(!isalnum(tmp1[i]))
                tmp1[i] = ' ';
        }

        p = strtok(tmp, " ");
        if(p)
            strcpy(s1[n++], p);
        while(p)
        {
            p = strtok(NULL, " ");
            if(p)
                strcpy(s1[n++], p);
        }

        p = strtok(tmp1, " ");
        if(p)
            strcpy(s2[m++], p);
        while(p)
        {
            p = strtok(NULL, " ");
            if(p)
                strcpy(s2[m++], p);
        }

        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                if(!strcmp(s1[i], s2[j]))
                    LCS[i+1][j+1] = LCS[i][j] + 1;
                else
                    LCS[i+1][j+1] = MAX(LCS[i+1][j], LCS[i][j+1]);
        printf("%2d. ", count++);

        if(c1!=j1 && c2!=j2)
            printf("Length of longest match: %2d\n", LCS[n][m]);
        else
            printf("Blank!\n");
    }
}

[howardcheng]

I'm at a complete loss to this problem. I tried everything that has been suggested about numeric character, when to print Blank!, etc. and still get WA. I'm quite sure that my LCS code is correct as I have solved many problems with this code. What else can be wrong?

Here is my code...I know I don't really need to use a dynamic array but I was trying everything to make sure that I don't somehow have access out of bounds.

Code: Select all

removed

[mf]

It seems like the last line of the judge's input doesn't have a terminating '\n'. Your code doesn't handle that correctly.

[howardcheng]

Thanks. It was the last line of input without \n that was (one of the many) problems. What a horrible problem statement.

[sobhan naderi]

note that you digits persist in the input string and you shouldn't replace them whict space.

[ranban282]

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
using namespace std;
int main()
{
	int count=0;
	while(1)
	{
		count++;
		vector<string> s,temp;
		char s1[100],s2;
		int flag=1;
		int p=0;
		int c1=0,c2=0;
		while(flag)
		{
			if((p=scanf("%[a-zA-Z0-9]",s1))==EOF)
			exit(0);
			if(p)
			s.push_back(s1);
			while(flag)
			{
				char c=getchar();
				if(isalnum(c))
				{
					ungetc(c,stdin);
					break;
				}	
				else if(c=='\n')
					flag=0;
				c1++;
			}
		}
		flag=1;
		while(flag)
		{			
			if((p=scanf("%[a-zA-Z0-9]",s1))==EOF)
				exit(0);
			if(p)
			temp.push_back(s1);
			while(flag)#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
using namespace std;
int main()
{
	int count=0;
	while(1)
	{
		count++;
		vector<string> s,temp;
		char s1[100],s2;
		int flag=1;
		int p=0;
		int c1=0,c2=0;
		while(flag)
		{
			if((p=scanf("%[a-zA-Z0-9]",s1))==EOF)
			exit(0);
			if(p)
			s.push_back(s1);
			while(flag)
			{
				char c=getchar();
				if(isalnum(c))
				{
					ungetc(c,stdin);
					break;
				}	
				else if(c=='\n')
					flag=0;
				c1++;
			}
		}
		flag=1;
		while(flag)
		{			
			if((p=scanf("%[a-zA-Z0-9]",s1))==EOF)
				exit(0);
			if(p)
			temp.push_back(s1);
			while(flag)
			{
				char c=getchar();
				if(isalnum(c))
				{
					ungetc(c,stdin);
					break;
				}	
				else if(c=='\n')
					flag=0;
				c2++;
			}
		}
//		cout<<s.size()<<temp.size()<<endl;
		if((s.size()==0 &&c1==1)||(temp.size()==0&&c2==1) )
		{
		printf("%2d. Blank!\n",count);
		continue;
		}
		vector<char> t(temp.size());
		vector<vector<char > > c(s.size(),t);
		vector<int> row (temp.size()+1,0);
		vector<vector<int> > cost(s.size()+1,row);
		for(int i=0;i<s.size();i++)
		{
			for(int j=0;j<temp.size();j++)
			{
				if(s[i]==temp[j])
				{
					cost[i+1][j+1]=cost[i][j]+1;
					c[i][j]='d';
				}	
				else 
				{
					if(cost[i][j+1]>cost[i+1][j])
					{cost[i+1][j+1]=cost[i][j+1];
						c[i][j]='u';
					}
					else
					{
						cost[i+1][j+1]=cost[i+1][j];
						c[i][j]='l';
					}
				}
			}
		}
		int siz=cost.back().back();
		printf("%2d. Length of longest match: %d\n",count,siz);
	}
	return 0;
}

			{
				char c=getchar();
				if(isalnum(c))
				{
					ungetc(c,stdin);
					break;
				}	
				else if(c=='\n')
					flag=0;
				c2++;
			}
		}
//		cout<<s.size()<<temp.size()<<endl;
		if((s.size()==0 &&c1==1)||(temp.size()==0&&c2==1) )
		{
		printf("%2d. Blank!\n",count);
		continue;
		}
		vector<char> t(temp.size());
		vector<vector<char > > c(s.size(),t);
		vector<int> row (temp.size()+1,0);
		vector<vector<int> > cost(s.size()+1,row);
		for(int i=0;i<s.size();i++)
		{
			for(int j=0;j<temp.size();j++)
			{
				if(s[i]==temp[j])
				{
					cost[i+1][j+1]=cost[i][j]+1;
					c[i][j]='d';
				}	
				else 
				{
					if(cost[i][j+1]>cost[i+1][j])
					{cost[i+1][j+1]=cost[i][j+1];
						c[i][j]='u';
					}
					else
					{
						cost[i+1][j+1]=cost[i+1][j];
						c[i][j]='l';
					}
				}
			}
		}
		int siz=cost.back().back();
		printf("%2d. Length of longest match: %d\n",count,siz);
	}
	return 0;
}

[andysoft]

I follow all the tricks as written above, but still I got WA. Look, are these elements of my solution right?:
1) Everything except 'a'..'z', '0'..'9' and 'A'..'Z' are printable punctuation characters, not the words.
2) I must output "Blank!" only when length of one of the inputted strings is 0 - zero.
3) Number of case must be aligned to field of width 2 AND ANSWER MUST BE ALIGNED TO FIELD OF WIDTH 2 (?)

And tell me is it right (i solve this problem in Pas) that I use just string type for inputting?

And PLEASE watch my code, I tried to make it easier to read:

Code: Select all

ACC now :)

[andysoft]

Code: Select all

a b c
a c

what is length of longest match? 1 or 2?

[Jan]

Code: Select all

a b c
a c

what is length of longest match? 1 or 2?

2.

[andysoft]

Thanx everyone!
Now (after long time) I solved this problem (for just 10 minutes) and got ACC from the first time! .
Spoiler:
----
I used algo very close to maximum increasing subsequence algo!
----

[amitjaspal]

Hi everyone , I am new to uva and i am getting Presentation Error in this problem.
Here's my code ....please tell me what is wrong in it:

Code: Select all

/*
 *  * @ author : Amit Jaspal(IIIT-Allahabad)
 *   */
#include <list>
#include<iostream>
#include <vector>
#include<map>
#include<string>
//#include<sstream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;

#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define ll long long int
#define sm (int)13e7 /* MAX_INT */

/* Functions */

struct node{
	int i;
};
bool operator<(const node &leftNode, const node &rightNode) {
		 if (leftNode.i != rightNode.i) return leftNode.i < rightNode.i; //for increasing order;
}		 
//string inttostr(int i){	ostringstream o;o<<i;return o.str();}


///////////////////////////.............Code starts from here............///////////////////////////////////////
int memo[600][600];
int x,y;
vector<string>a,b; 

int lcs(int i,int j){
	if(i<x && j<y){
		if(memo[i][j]==0){
				if(a[i]==b[j]){
						memo[i][j]=1+lcs(i+1,j+1);// ?? why not i+1,j+1
						return memo[i][j];
				}else{
						memo[i][j]=max(lcs(i,j+1),lcs(i+1,j));
						return memo[i][j];
				}	
		}else{
				return memo[i][j];
		}
	}else{
			return 0;
	}		
}		

int main(){
	
	int i,j,count=0;;
	
	char ch;
	while(1){
			string s[600],s1[600];
			int i1=0,flag=0,i2=0;
			int yy=0,zz=0;
			// Taking the first string as input 
			while(ch=getchar()){
				
				if(ch=='\n' || ch==EOF){
					if(s[i1].size()>0){
					a.push_back(s[i1]);}
					if(ch==EOF){
						flag=1;}
					break;
				}
				else if((ch>=65 && ch<=90) || (ch>=97 && ch <=122) ||(ch>=48 && ch<=57)){
					s[i1]=s[i1]+ch;
				}
				else{ 
					if(s[i1].size()>0){
						a.push_back(s[i1]);
					}	
					i1++;
				}
				yy++;	
			}
			/*for(i=0;i<a.size();i++){
					cout<<a[i]<<"  ";
			}
			cout<<endl;*/

			if(flag==1){break;}
			
			// Taking the second string as input
			while(ch=getchar()){
				
				if(ch=='\n' || ch==EOF){
					if(s1[i2].size()>0){
					b.push_back(s1[i2]);}
					if(ch==EOF){
						flag=1;}
					break;
				}
				else if((ch>=65 && ch<=90) || (ch>=97 && ch <=122) || (ch>=48 && ch<=57)){
					s1[i2]=s1[i2]+ch;
				}
				else{ 
					if(s1[i2].size()>0){
						b.push_back(s1[i2]);
					}	
					i2++;
				}
				zz++;	
			}
			/*for(i=0;i<b.size();i++){
					cout<<b[i]<<"  ";
			}
			cout<<endl;*/		
		//	cout<<yy<<"          "<<zz<<endl;
			count++;
			x=a.size();
			y=b.size();
			if(yy<=1 || zz<=1){
				cout<<count<<". Blank!"<<endl;
				//count++;
				if(flag==1){break;}
				else {continue;}
				}
			//cout<<x<<"    kkkkkkkkkkkkkkk    "<<y<<endl;
			
			
			// Applying D.P
			for( i=0;i<=x;i++){
				for( j=0;j<=y;j++){
					memo[i][j]=0;
				}
			}
			//a.clear();
			//b.clear();	
			int length=lcs(0,0);
			//if(length!=0){
			cout<<count<<". Length of longest match: "<<length<<endl;
			//}else{}
			a.clear();
			b.clear();	
			
			if(flag==1){
				break;
			}	
	}		
	
	return 0;
}	

[Obaida]

Some one please help me to get accepted. (I am getting wa constantly!!! )
here is my code:-

Code: Select all

#include<iostream>
#include<sstream>
#include<vector>
#include<cstring>
#include<string>
using namespace std;

int c[503][503];

int lcs(vector<string>x,vector<string>y){
	int i,j,max=0;
	for(i=0;i<x.size();i++)for(j=0;j<y.size();j++)c[i][j]=0;
	for(i=1;i<x.size();i++){
		for(j=1;j<y.size();j++){
			if(x[i]==y[j]){
				c[i][j]=c[i-1][j-1]+1;
				if(c[i][j]>max)max=c[i][j];
			}else if(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];
			else c[i][j]=c[i][j-1];
		}
	}return max;
}

int main(){
	char st[1001];vector<string>s1,s2;bool flag=1;s1.push_back("*");s2.push_back("#");int ca=0,i;
	while(gets(st)){
		string temp;
		if(flag){
			for(i=0;st[i];i++){
				if(!isdigit(st[i])&&!isalpha(st[i])&&temp.size()){
					s1.push_back(temp);temp.erase(temp.begin(),temp.end());
				}
				else temp+=st[i];
			}if(temp.size()){s1.push_back(temp);temp.erase(temp.begin(),temp.end());}flag=0;
		}
		else{
			for(i=0;st[i];i++){
				if(!isdigit(st[i])&&!isalpha(st[i])&&temp.size()){
					s2.push_back(temp);temp.erase(temp.begin(),temp.end());
				}
				else temp+=st[i];
			}if(temp.size())s2.push_back(temp);temp.erase(temp.begin(),temp.end());flag=1;
			if(s1.size()>1&&s2.size()>1){
				int res=lcs(s1,s2);printf("%2d. Length of longest match: %d\n",++ca,res);
			}else printf("%2d. Blank!\n",++ca);
			s1.erase(s1.begin()+1,s1.end());s2.erase(s2.begin()+1,s2.end());
		}
	}
	return 0;
}

[farhan_iut]

I m getting Runtime Error in this code.. Please anyone help...

Code: Select all

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
#define S 5000
int dp[1000][1000],la,lb;
string sa[S],sb[S];
char a[10000],b[10000];

int max(int a,int b){
	if(a>=b)return a;
	return b;
}

int doit(int p1, int p2){
	if(p1>=la||p2>=lb) return 0;
	int &ret= dp[p1][p2];
	if(ret>-1) return ret;

	int a,b,c=0;
	a=doit(p1+1,p2);
	b=doit(p1,p2+1);

	if(sa[p1]==sb[p2]) c=doit(p1+1,p2+1)+1;
	return ret= max(a,max(b,c));
	
}

int main(){
	freopen("10100.txt","r",stdin);
	int i,j,k,l,cas=1;
	while(gets(a)&&gets(b)){
		if(!strlen(a)||!strlen(b)) printf("%2d. Blank!\n",cas);
		else{
			char c[100][1000],d[100][1000];
			k=0,l=0;
			for(i=0;i<strlen(a)+1;i++){
				if((a[i]>64&&a[i]<91) || (a[i]>96&&a[i]<123 || a[i]>47&&a[i]<58)){
					c[k][l]=a[i];
					l++;
				}
				else{
					c[k][l]='\0';
					if(l) sa[k]=c[k];
					k++; l=0;
				}
			}
			la=k;
			if(a[strlen(a)-1]=='.') la--;
			k=0; l=0;
			for(i=0;i<strlen(b)+1;i++){
				if((b[i]>64&&b[i]<91) || (b[i]>96&&b[i]<123 || b[i]>47&&b[i]<58)){
					d[k][l]=b[i];
					l++;
				}
				else{
					d[k][l]='\0';
					if(l) sb[k]=d[k];
					k++; l=0;
				}
			}
			lb=k;
			if(b[strlen(b)-1]=='.') lb--;
			memset(dp,-1,sizeof(dp));
			int r=doit(0,0);
			printf("%2d. Length of longest match: %d\n",cas,r);
		}
			cas++;
	}
	return 0;
}

[fkrafi]

Code: Select all

Got AC... thanks Shafaet_du 

[Shafaet_du]

hello world this is me
,.,me hello this
.,;''l'
34dsf
sdf

sdf me and what the hel.,/ is sd
sdfg asde what the asdasd is sd

output:

Code: Select all

 1. Length of longest match: 2
 2. Length of longest match: 0
 3. Blank!
 4. Length of longest match: 4