10100 - Longest Match

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

Moderator: Board moderators

fkrafi
New poster
Posts: 13
Joined: Wed Sep 15, 2010 1:36 pm

Re: 10100 - Longest Match

Post by fkrafi » Tue Oct 05, 2010 5:42 pm

my code also gives the same output.... but why wa..........

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10100 - Longest Match

Post by Shafaet_du » Wed Oct 06, 2010 6:29 pm

@Fkrali:

Your code will produce wrong output in this case:

Code: Select all

hello world
HELLO
Your output is 1 where it should be 0. just ignore capital letters and you'll get ac.

jucmes
New poster
Posts: 1
Joined: Sat Nov 03, 2012 7:38 am

Re: 10100 - Longest Match

Post by jucmes » Sat Nov 03, 2012 7:43 am

Hi, could you help me here? I keep getting runtime error and I don't know why.

Code: Select all

#include <iostream>
#include <string>
#include <stdio.h>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <ctype.h>
#include <string.h>
using namespace std;

string arr1[1002];
string arr2[1002];
int arrDef[1002][1002];
int procesarLinea (string a, string arr[1002]);

int main()
{
	int cont = 1;
	string a, b;
	
	while (getline(cin, a))
	{
		memset(arrDef, 0, sizeof arrDef);
		memset(arr1, 0, sizeof arr1);
		memset(arr2, 0, sizeof arr2);
		int numPalabras1, numPalabras2;

		getline(cin, b);

		if (a.size() == 0 || b.size() == 0)
		{
			cout << cont << ". Blank!" << endl;
		}

		else
		{
			int numLetras = 0;
			string::iterator it = a.begin();

			for (int i = 0; i < a.size(); i++) 
			{
				if (numLetras == 0 && a[i] == ' ') 
				{
					a.erase(it);
					i=-1;
				}
				else if (isalnum(a[i])) 
				{
					numLetras++;
					it++;
				}
				else if (numLetras > 0 && a[i] == ' ' && i < a.size()-1 && a[i+1] == ' ') 
				{
					a.erase(it);
					i--;
				}
				else it++;
			}

			numLetras = 0;
			it = b.begin();

			for (int i = 0; i < b.size(); i++)
			{
				if (numLetras == 0 && b[i] == ' ') 
				{
					b.erase(it);
					i = -1;
				}
				else if (isalnum(b[i])) 
				{
					numLetras++;
					it++;
				}
				else if (numLetras > 0 && b[i] == ' ' && i < b.size()-1 && b[i+1] == ' ') 
				{
					b.erase(it);
					i--;
				}
				else it++;
			}

			numPalabras1 = procesarLinea(a, arr1);
			numPalabras2 = procesarLinea(b, arr2);

			for (int i = 1; i <= numPalabras1; i++)
			{
				for (int j = 1; j <= numPalabras2; j++)
				{
					if (arr1[i-1] == arr2[j-1])
					{
						arrDef[i][j] = arrDef[i-1][j-1] + 1;
					}

					else
					{
						arrDef[i][j] = max (arrDef[i][j-1], arrDef[i-1][j]);
					}
				}
			}
			cout << cont << ". Length of longest match:";
			cout << setw(2);
			cout << arrDef[numPalabras1][numPalabras2] << endl;
		}
		cont++;
	}

	return 0;
}


int procesarLinea (string a, string arr[1002])
{
	int numPalabras = 1;
	int numPalabrasDef = 0;
	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] >= 'A' && a[i] <= 'Z')
		{
			numPalabrasDef = numPalabras;
			a[i] = tolower(a[i]);
			arr[numPalabras-1] = arr[numPalabras-1] + a[i];
		}
		else if (isalnum(a[i]))
		{
			numPalabrasDef = numPalabras;
			arr[numPalabras-1] = arr[numPalabras-1] + a[i];
		}
		else 
		{
			numPalabras++;
		}
	}
	return numPalabrasDef;

}
Thanks a lot!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10100 - Longest Match

Post by brianfry713 » Wed Nov 07, 2012 12:35 am

On the sample input your code is producing a seg fault during procesarLinea().
Check input and AC output for thousands of problems on uDebug!

asmaa
New poster
Posts: 4
Joined: Thu Jul 04, 2013 11:25 pm

why this code give me Presentation error every time :(

Post by asmaa » Sat Jul 06, 2013 1:46 am

finaly AC...
thank you Mr brianfry713 very much :D
Last edited by asmaa on Thu Jul 11, 2013 2:31 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10100 - Longest Match

Post by brianfry713 » Mon Jul 08, 2013 11:28 pm

you have to output a line starting with the case number right justified in a field width of two
Check input and AC output for thousands of problems on uDebug!

asmaa
New poster
Posts: 4
Joined: Thu Jul 04, 2013 11:25 pm

Re: 10100 - Longest Match

Post by asmaa » Tue Jul 09, 2013 7:20 pm

cout<<count<<". Length of longest match: "<<LCS[v2.size()][v1.size()]<<endl;
what is wrong with this?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10100 - Longest Match

Post by brianfry713 » Tue Jul 09, 2013 10:20 pm

For the sample input, your output is:

Code: Select all

1. Length of longest match: 1
2. Blank!
3. Length of longest match: 2
The correct output is:

Code: Select all

 1. Length of longest match: 1
 2. Blank!
 3. Length of longest match: 2
Check input and AC output for thousands of problems on uDebug!

asmaa
New poster
Posts: 4
Joined: Thu Jul 04, 2013 11:25 pm

Re: 10100 - Longest Match

Post by asmaa » Tue Jul 09, 2013 10:59 pm

I made it :
cout<<" "<<count<<". Blank!"<<endl; and cout<<" "<<count<<". Length of longest match: "<<LCS[v2.size()][v1.size()]<<endl;
but i still have PE :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10100 - Longest Match

Post by brianfry713 » Wed Jul 10, 2013 10:07 pm

Try input:

Code: Select all

This is a test.
test
Hello!

The document provides late-breaking information
late breaking.
This is a test.
test
Hello!

The document provides late-breaking information
late breaking.
This is a test.
test
Hello!

The document provides late-breaking information
late breaking.
This is a test.
test
Hello!

The document provides late-breaking information
late breaking.
Output should be:

Code: Select all

 1. Length of longest match: 1
 2. Blank!
 3. Length of longest match: 2
 4. Length of longest match: 1
 5. Blank!
 6. Length of longest match: 2
 7. Length of longest match: 1
 8. Blank!
 9. Length of longest match: 2
10. Length of longest match: 1
11. Blank!
12. Length of longest match: 2
Check input and AC output for thousands of problems on uDebug!

jalil_cse
New poster
Posts: 8
Joined: Tue Dec 25, 2012 12:35 pm

Re: 10100 - Longest Match

Post by jalil_cse » Fri Dec 20, 2013 9:22 pm

why wa plz help me........

Code: Select all

thank you brianfry713
Last edited by jalil_cse on Sun Dec 22, 2013 5:57 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10100 - Longest Match

Post by brianfry713 » Sun Dec 22, 2013 3:00 am

output a line starting with the case number right justified in a field width of two
Check input and AC output for thousands of problems on uDebug!

sheldrake
New poster
Posts: 1
Joined: Mon Jul 14, 2014 7:37 pm

Re: 10100 - Longest Match

Post by sheldrake » Sat Aug 02, 2014 8:31 am

Code: Select all

AC

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

Re: 10100 - Longest Match

Post by gr81 » Tue Sep 16, 2014 7:16 am

brianfry713 wrote:Input:
a!aa!aaa!
aa
Output should be 2.
I guess we are counting words which gets matches, even uDebug gives output 1.

Output should be 1.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10100 - Longest Match

Post by brianfry713 » Tue Sep 16, 2014 8:07 pm

Yes, that output should be 1.
Try input:

Code: Select all

The document provides late-breaking information
late breaking.
aaa a a a a 
a 
AC output:

Code: Select all

 1. Length of longest match: 2
 2. Length of longest match: 1
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”