10405 - Longest Common Subsequence

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

Moderator: Board moderators

ashish_thakur
New poster
Posts: 7
Joined: Mon Dec 22, 2008 3:00 pm

Re: 10405 - Longest Common Subsequence

Post by ashish_thakur » Tue Dec 23, 2008 6:09 pm

thanks for the insight I have corrected the flaw. It's accepted

sh415
New poster
Posts: 13
Joined: Fri Nov 13, 2009 9:31 am
Location: JU

Re: 10405 - Longest Common Subsequence

Post by sh415 » Sun Oct 31, 2010 4:46 pm

getting frequent WA; dont know why...............
I have taken input through gets and then used LCS algorithm;
is there any thing critical or wrong?????

anan_xon
New poster
Posts: 1
Joined: Mon Dec 13, 2010 2:04 pm

Re: 10405 - Longest Common Subsequence......getting CA...plz

Post by anan_xon » Sun Aug 14, 2011 6:31 am

#include<iostream>
using namespace std;

int len(char *a)
{
int i=0;
while(a!=0)i++;
return i;
}

int lcs(char *s,char *t)
{
int **table;
int i,j;
int max=0;

int m=len(s);
int n=len(t);
table=new int*[m+1];
for(i=0;i<=m;i++)table=new int[n+1];


for(i=0;i<=m;i++)
{
for(j=0;j<=n;j++)
{
if(i==0 || j==0)table[j]=0;
else if(s[i-1]==t[j-1])
{
table[j]=table[i-1][j-1]+1;
if(table[j]>max)max=table[j];
}
else
{
if(table[i-1][j]>=table[j-1])table[j]=table[i-1][j];
else table[j]=table[j-1];
}

}

}


return max;
}

int main()
{
char s[1001],t[1001];
while(gets(s) && gets(t))
{
int q=lcs(s,t);
cout<<q<<endl;
}

return 0;
}

limitedmage
New poster
Posts: 1
Joined: Mon Aug 29, 2011 10:20 am

Re: 10405 - Longest Common Subsequence

Post by limitedmage » Mon Aug 29, 2011 10:22 am

I'm getting WA and I have no idea why. What could be wrong?

Code: Select all

#include <cstdio>
#include <cstring>

char a[1010];
char b[1010];
int dyn[1010][1010];

int lcs() {
    int ca = strlen(a);
    int cb = strlen(b);

    for (int i = 0; i < ca; i++) {
        for (int j = 0; j < cb; j++) {
            int curr = 0;
            if (j > 0) {
                curr += dyn[i][j - 1];
            }

            if (a[i] == b[j]) {
                curr += 1;
            }

            if (i > 0 && curr < dyn[i - 1][j]) {
                curr = dyn[i - 1][j];
            }
            dyn[i][j] = curr;
        }
    }

    if (ca == 0) {
        return 0;
    }

    return dyn[ca - 1][cb - 1];
}

int main() {
    while (gets(a)) {
        gets(b);

        printf("%d\n", lcs());
    }

    return 0;
}

a.elbashandy
New poster
Posts: 12
Joined: Fri Dec 23, 2011 6:23 pm

Re: 10405 - Longest Common Subsequence

Post by a.elbashandy » Fri Dec 23, 2011 6:33 pm

my code seems to be right but i get WA !!! can anyone help me ??


Code: Select all

#include <iostream>
#include <stdio.h>

using namespace std;

int main()
{
    char line1[1010];
    char line2[1010];
    while(gets(line1) && gets(line2))
    {
        char c,d;
        int i = 0,j = 0,saved_j = 0,sum = 0,msum = 0,flag = 0,counter = 0;
        c = line1[i]; d = line2[j];
        while(c != '\0')
        {
            j = saved_j;
            flag = 0;
            while(d != '\0')
            {
                if(line1[i] == line2[j]){
                    sum++;
                    flag = 1; i++; j++;
                    saved_j = j;
                    c = line1[i];
                    d = line2[j];
                    break;
                }
                j++;
                d = line2[j];
                flag = 0;
            }
            if(flag == 1 && c!='\0')
            {
                continue;
            }
            if(c != '\0'){ i++; c = line1[i]; }
            d = line2[saved_j];
            if(c == '\0')
            {
                if(msum < sum)
                    msum = sum;
                sum = 0;
                counter++;
                c = line1[counter];
                i = counter;
                d = line2[0];
                saved_j = 0;
            }
        }
        cout<<msum<<endl;
    }
    return 0;
}

davdigsb
New poster
Posts: 2
Joined: Fri Jan 06, 2012 3:33 pm

Re: 10405 - Longest Common Subsequence

Post by davdigsb » Tue Jan 10, 2012 4:32 pm

you sure you posted it in the right section?

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

Re: 10405 - Longest Common Subsequence

Post by brianfry713 » Wed Jan 11, 2012 2:08 am

Check input and AC output for thousands of problems on uDebug!

vpanait
New poster
Posts: 17
Joined: Sun Apr 01, 2012 11:01 am

Re: 10405 - Longest Common Subsequence

Post by vpanait » Thu Oct 04, 2012 10:34 am

use fgets() to parse the input, I previously used "cin" that stops at "spaces" and was getting WA, so i presume "space" is a valid part of the input and needs to be processed

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

Re: 10405 - Longest Common Subsequence

Post by moxlotus » Sun Apr 07, 2013 6:43 am

Whats wrong with my code??? I can pass the test cases posted on this thread but still getting WA. Can someone post more test cases? Thanks in advance.

Code: Select all

#include <stdio.h>
#include <string.h>
#define MAX 1002

int LCS(char [], char []);

int main(int argc, char** argv)
{
	char str1[MAX], str2[MAX];
	while (gets(str1) != NULL) 
	{
		gets(str2);
		printf("%d\n", LCS(str1, str2));
	}
	return 0;
}

int LCS(char str1[], char str2[])
{
	int i, j, k = 0, l = 0, m = 0;
	int max = 0;
	int len1 = strlen(str1);
	int len2 = strlen(str2);
	int p;
	for(p = 0; p < len1; p++)
	{
		k = 0;
		l = 0;
		for(i = p; i < len1; i++)
		{

			for(j = l; j < len2; j++)
			{
				if(str1[i] == str2[j])
				{
					l=j+1;
					k++;
					break;
				}
			}
		}
		if(k > max) max = k;

	}

	for(p = 0; p < len2; p++)
	{
		l = 0;
		m = 0;
		for(i = p; i < len2; i++)
		{
			for(j = l; j < len1; j++)
			{
				if(str2[i] == str1[j])
				{
					l = j+1;
					m++;
					break;
				}
			}
		}
		if( m > max) max = m;
	}

	return max;
}

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

Re: 10405 - Longest Common Subsequence

Post by brianfry713 » Tue Apr 09, 2013 3:54 am

Input:

Code: Select all

pgddggnujxqetuchfwhidygnsyksszhhhkmntbhczaiswkzbiikmisbasnuloduyqhllkvpjxxdtjeurogfwzjz
wtenzblrkycutrgsollzsiqgowdphcjdxpsysdpcctzvkfqasbzkjstaqyrxcaabsvakyrpaloyvvoy
rzadrtdhtuevxhwrcwbaoqdzgdwbrupkurnlkqvdnzamg
dktgljzqkftgjmdywxpkkbcfgphgdneiyzpliqdsxwbgkeggbxsnavtimaqspvapupcdhhxffynpcuyfrq
snoaaqruhouzimdntllaqlogqievbwq
kgymyrgifahnmmdixoiobwwrg
piyfdiobwoscwzffntsqbrgkfhgdbnfqxevaolelcypaywgnqafrtndbumevbknyojyewerydjzdfhqxjxrckudggieh
rhkciozmgzrpauwjmusjlxtfcaomgxgxfqanhbbnctednaoauhlfgfnkhdxpcfmhyowfryuuryzgynivwu
ebppkuozxt
gtcfytdspwqoerenmajofmgwwckxzdkixonxisszqkqubujpwsgdemzcojbqpmaoapnkh
kxqattwdjsxpwedxgtjijawlowadjhjtgzvasrfdlcujgxhprszasxoivolewuzevugqnltzqoiyn
pejqhdnvljjxnhtnmpjuhxicwyqgweaoklerpsmcbybqfvftm
ovowxmwqsuwuiggnaxhmzkmdauainmzdjnbgzzwtusocbwrbvypwkczlwzvlnurwjsfkubdowtszrmamk
jvvkirkffzbwykqdukgzyevtdmffbrxmoswymidrkepiqflkstmsyhlbvsjwkiiachzorch
jylzgwmyqyqqfetawczikjj
qkdkmnnxlzxrxlppjifqmzs
drvodgdvqifcvtchubytmqjxyqnm
hyvbtlebozrwfwuaybwzbplrakrrxfiggfhbqldglufsqzsoaqpdfaxgmozjwjscpzfflioydtqvskmuabxfe
nqlmcjwulltqsgbgegbubvenpgppmvlbly
nhmhuzdntjocoudk
zrlqxcflztnkrdazrjvsmilywpostyqupdknhsygnnsequfje
bslpskegczfutwzgjiykonxjrqdzz
cdcnsuzybeyiyteazqizazmxigplhpvjuzymvymyekicgnefdnffmtewbuhijerffsrdsfbwqkawzfdeskj
encfhlqsshxxbqat
eroqsmpzpttcczirdpzoftiptgqjimhodvexjtwzopbqqjktajkg
svxyljjzqxdoccxxzymobefmoanzktgdoddbmmbfmgtqiqnjpbaqihdwhqyslexzhaawndbblwrumgfdkfwsmbqw
oqcsndcnfacjdduzwqndytpdphsqxqjogngtqkgxklipo
onvcsvvhzmqtcnjndpakkswsrjdayufphctbyoizcysgndtruvdepbygkcgjylahotiojqnlqfrdkmwejziybgglkpwicwrsp
gartlhaelkqjozjyzmfgzrvwczutsmtymksause
dxqtwzsylzglqdjscfoutjt
vnkpfowklnekowiavqnntyivfwqzfl
aytqfhoqvbwhqspspffeafmvkknlrausynkexawucsbumsmbzthzauwkgmwymqsngctfcpbghcctuowvjdujzswggsetkwisa
zeq
nxcpsygotrtpbtkzbqrhldfvwfwvlmwylaqfbwtwnpoqkyplqisemxzkewfpkdqyegdh
zdrorkarzlkkfowcngilnzwtpwzxzgbajv
dfqugbesiuokiwutmurfjnejpkkrvhiymyvvcbnkwexgcrzonttxizizjsrfazfozaldczqafpghghwuartlrbkc
dhxepoepzjtaztfobpxjntleowxrjaomjmryaxqbgjcifjygyxrlqdqgbpxkpmxzaqzanpbvbfdipcqnbizslramgyzymwzoo
qbqrytzcbogrdhzcbmvcbecaeqyd
mdupvnnqorrczlgjmkkzioamscskavqmambyaoooiithvbqhldivtkhmmbym
pyzb
zdspuaznjuqacbdkxwvgkjijwgawhbyihqabszqbugdwhgigffprpzcnhcjrgjbnbbqtbgxvmatvj
eqlvhcwmpdqawymylnzdjcjizvisttyxjjutn
fevvesusshgtlrwwzvuhqnbqmmbgfoymstkyngrhpzbcqzzpwtyoibeuohcvvaipvsqjyjqnitqasrppmpfurm
htscrumipeyaehrurkmrfdiwpybjrnbyjvcappigvjhcsawkkibrnmnckpnbeqbn
fncuyishrubrsleapvpbjrnagqewruhyhjvhtnqljscbfidwesxpjmprcvn
pwuzhpgccznntsoyarvgjuvujmlliahxydyfshjwgxjzrzztqwaztxtckgnuiwtgzsntzwrhvaimzhirgkszhnbttqpbpjh
dwketb
qetffcnxixpjg
mcwfraucjkh
wlbyyteryjwlggkystbevz
obftlqatoowmmpqgocebikmgchjjejuskanxsqsgeovsgnywpcxaplitsscwdzrpbgntwhbcyyveotafyzfnlogfilelkvcnbpi
zjcxkxbytddrcl
pbmvjzzwlwyyzqgzpsemcdpcwshpusvkvkhelgcxebxdtefiylucolendnexicjdoqizymyenwkgcrqc
mesxkhaxoafqljeetfefgjvcvdgmuiqimkgyuivikbawmgahlgorpjvmpdyllqtzdbxxkvfwyfsklutybhssrpfitftgwm
zqfy
ad
akrkxlfxonphef
oathgrvosluqnwvmxfdjeqpchetokacyaxfhpavhmrabqvnpdsahlrlsvhifhkdijiryloizgiaydonginqtfdnckv
shlcrwvphjzirh
pnycvhslczpqbbnltvxxmvudeefmvmunbtrxcliekzwobkzwhywvvqazuflsuihvdysfkdlwckmdwmcdmy
ioyhlevdydmvikopwrattmhzitblgblopmxassfsxrnhebwauzvqldpwysjgtxwkjulbostokivqmu
gtowgtnerhoyalulwqyxhqsvccssoolxjztqsj
lqkltxggtyesfwmc
pvtfjectfylzhjlxuwqtewpdcjkbwncnkvuvcxqhvbhclubhsucxsrcvbmwzbaolvihxhxhcbqg
kkxcezbwtftwurvvrlhpvqmdpvfqloexydcedfawlwsfppchclwxbkariijtwqtwtvayacunaosqfvxjgv
khjdprmlpeelyznwbstpsjhipehynehzmrcdkqoavuntvdrxvkmpwvylchlrmvqamsfyiwydq
ymrqjocxdaudnwlznxwfzkxeigajltxkfqcqggpjhjnuiyvxxtdydccmkfxwauifmmxsso
bxqyhqvhprmnuosizzfxzbfgprdhlrlpqdpaumhjdvzylrimsojrrqxhjcqvvbmlhbndpwmtrntdgbpyrbpjros
qiynmkztnmwclkxcaqhguzflawwtloudxurlgsetgcyroxwoodvkcaveysylgupfpiqvcwriypcnoybedwoiykmzc
kkhbswjirnfi
fzauoawsduhlvtauxmejtgbprkjhrtfytftjhrdklmyifycckjmgrpxkbgrsawtvdmemdhxquxzbxbejmspdhn
jtfdveyqjkwwpgviashdpkjyxbqcldqwyyzwcymnkjjcrekryrwpdgqchgfu
vqjtsfxsuncfwgwdqpd
ltprjrzpwvaumlnernwlaaqyhmdzbhlmaaglrfcoceiopxsgmqt
tlnczqdaxopzovmgcowgsgvifpqsimgbxvdxmizlxqnlnztrqrykztufklzsxhtwdytrhveglrrbtn
lgsvgnqlydmqatmywkuptpuzcltdggyroqnugdhe
tu
pgintcdorxowkhbrpb
duxaachekbauqhdfcfiqzfgvsnyleavkuv
uxtykwyeohjujpccqkilcyjpelkoffazfuxpsythhdbtudvkpfxtdiikutazabzfxyupyqygtz
pfuzubyofgwpcrpcssdxrdujckhkfhjumfvigtwnbvceouiiolggqcp
myerfnntsicbdaoevtkmnsudfcjweaqqzvjgkwcfgegjewqcpcqexkicntarwrkxotdasffallksicuzgmed
oglhgfdzpcpkgqenvfzjrrtvnubzyfxoljwtobvfemrmcwzabals
gpiaqjzvhpisleipznvlejqaisdldxejmpjdykahajz
nheowzbbirdtjjgogmxvb
yatyjvjjjwsnmpposzhxurgafpnfkqoishicdsnoqfdfwstquaootwrblegvwuf
dorgigualafku
aodqdwnwzyafuybznfpglzmicakjmekm
nfylsulqwsmuuokzfqmhfwjhgstlehgtmehgauxwmlsgbchhtuqaszhztamajstwyccywbujpmrqpzzkvpmnqtokvcmeufcskfq
imrxbjqskrchhqwzjnlgpxkmfpepuxxelpemawemnitwypwjehpufcgkrmbnlytznx
ntszjcufdmboqlekqiscbfdosbhrphfecxglbcteoutfhzrzjkbkrea
ijdzqifvfngiqbpewilfjff
pgeinetxnwwgebblpjuhljnjtz
eetyvccdrgwovvkbzncneohlzszknyyr
upbytepzcdwznyzccmhqvsrnrdcrctxykywdenej
aifyjhdxovshphasjuwetuousryf
jvwuawdkbbyxvhmdkeogbtzxhtszuzwfvuzxtdjugitbrhgbovhrojoxeiwai
gfrhekmohsyawpkctyxcpnlflsojsyeadyihiuxrp
unlepecpgtcuypmozgmfjpdrzonwfeuzrfdjlhytacnzsbpricyrtckusztxenz
ucgfkeykj
lbpbuzfssywe
qeookbnhvrqcdwcqfsbgiecjjxekvidmmrayupgrgwtmsxcaqdiaklj
inddyipkbrjvirmrphdjffjxksxufiqnytswekifbtdkkrdbbgnilwfxqcs
kikidfghppp
iscvlhwmnjuaizyydswoaiydnhncwcvewzzhhyuwhoxpqxqtpojpykumrjqnlnth
tpwtluazrspoklfauuyerkvadkoqexfzmdszyuzroqiydnyykzedladomthqrmrfslfqggjuy
vcfvarueuggzwvtdlmqfrkqycyeltddqfklhbgnvowukrpocbgjvqatsyadtdijksvrvdgqrcnbtcrygxhbnjwhkwndzvpl
melpleinrl
vdfdcoeqydzizmnbicmyorlfepn
ibaeefjiwqyutac
mrvwukuidiqhxfyggbmmivvelvygvczkuwgqgdajlqqkwrqesetacohplfwjkx
gtzwaewjpncaltspnxipbywqmemvqjowfpsfuqqldulqpeicdsugrqwfwlamwqi
fcibtbnyvyrlezpjr
pkcopyzpnxfxznajovmbvicmvilmsfwjpazfaywnyelzrnihivlffpscx
orkkdamchndfabjnacakmifxommiolndfapiack
rporqyf
cfdoqklgxzqlndqsdgcfkoobefuwfzrhhuyzglhdnxracjugpwnbmecqjxpqygxhcxiijpowohyrqs
iqmlcqovznkpnspvumfexxstlbrculbebopgefbgsnvifmfbbkfyhautbnxxzzbcpritwlzraxzflggmqonaohvrusp
tqyijieiwfzweac
ikeaaraqavixqzslrswbbajxhktmmxewkkwkexbeulbmkwybouepwpofbktphxltiiemhhsdswqcsq
gkkyibopdyjsigebqohexozagvqkpgqvscvcdmsgkbbujhwcvdgsuhsacllrtdpofmqiykrjlsfxzbzwhhobpidtvonptcfyo
jpicavufsvhtrqdhturwnnncegejhvgqmosmkorejayaqdhjxygmntprbvcisjyezsqlgkqpkqrbtymszuempvg
tizltasvukgduwsfomihmwblrgagdizwqbimbchxmpahovochwmtunhlvjuzrtvjwfxzhgxwwxdksro
paxlqgxlptmimktlprkzxhvvfahztwbkyavogscxlqfaaalsrvtrfoomqwljuotsqojwjnvwdcyedlywjrpofecxcngwe
ourztcmozqrzwunuqylio
mqpodxkjya
pazsonteeucahytfjbtdpjudprpappghrfzgvumborcwpvdbyzenkzsbshckykrsssanmmoadsyv
ewndccpdurwdvgcfxwxpwmbkbdqteljihynjbcpvtlbordwqb
hxikhlnzerkpbtoofrruokfpbyuzovuvuehepudwoonphdeouvilhnaknxldsia
mhtecwasmphutnipitasidewaqzuyajkjcqnzsflinhdasslnvfvyjryztsxvekeg
shtzvbmeepyyclthjtqcrsvmpssbzyctivsf
hleykcaxyjgrzjltgzlzrmarotbllglssrqewsdubkndvywbxhcqucikxjyjsjdmbwqxottsfgvchrgg
kxvnhfkqfvkrbwuxotnkmfruaubuaivkhszozmgfjrwknqjcjxmxcdrfz
bbdwmkonypbgulxqxlihpredoiigpibqjgoxqenquowobwhbhpiyjobxyjfqtiido
cgdpyzgxqjtxkcouaxkdxjocbinjnbgpimhilnfbyayjcpfeo
hlbwqcgdlteukogt
rievhfvsjkxozpxkqvcsbfgwmahcicbzlgwsnsmycjodzmqphskjyqhksqmatobewyylqkl
vayumomvgyggooqiefixvldtjdgbnrwjtuffkrdqrjxfxppewzdrljmwmsycmunfqsnamqsdzplzhcfd
kxptjlielkqfzvxrixfaqlchydqaiuesttochwgsgyafuxyexgfpthyrkptulaoetcicyrvgpxnlwmqtux
nglgsazmnz
rvfbxd
umitzvqlllhkwuqhaijcwydxpyesyjlsvvovqeiepqonmhwpphrmfulwvpptaanwxbtnfdtxvkkirhxgqquwmfsh
hazjovgrqwxtpwpbgzspybgoveadwibgkapaxysnurjlnanvzhlxitngxplvzmbmptmmreclxnyknnimvvlfoalnryktlmfcfr
yyslxfjkuzsiwntbdvpsnncgaq
cxetvengcvsmpreynttqwphoe
smxjzaifvekimmdeavxetmxofvfmljjdxhoyhzecfomrcsycnxiikhwpccb
nns
ujlbipfnftgjlenyevgocffghivwvqjpzvshmzwstcbgjpfnmndrsizbsvyolhfmeav
zrjutmbcdirqxujqcirxdrl
bscfsxwuqhqmwtozdirbcarhlkeqerjfjlkeljadsspomgqpojsqmjxxwdnauwhgktmxem
xeqnswdkmpccbocykhnmckviwouttivqolfhjlrvavabjebv
ojpyezwtvpodlgsylbkwufyphzznawzrgqrkqofldtrqblrnmblgikxqlyfovgfbxwnnmvasqrisczhqa
ylewdsuigppnsmlibydbqtvanzcuqepoptmslhbtysgteubhugkk
fmpfojxtyniuabfhebhwhacddjxjvhlbwaiklhdkumgupldtmlr
ntbrezcbineepopbvsnqgtmxgssvdjtseulktomcbqirfxucsjsachykzqfecywgtitowfqzxzseyohqxbtzirkj
rnlqmulwnzuusvttoyrchkaidbtwncffstvgnicchyyztruhrom
yojdpcbdggiyzfgoniqwiqycislbgzagnjjfnmkttsuuzaloldktuivedj
jihsysddfqnzjhtfgvswgwgaqrxwwgbfrlzpddslthmeohjwces
aajstgopprxicwxizrtsyfwomikom
xogigcrwripqqsnncogvhecfuopgedketsobufxonpefhtsliairgkyaaqggtskpnzqhgqxwfcbovwzdwjwdtvdtlm
gemvrnobtgyplctbypcdllaoevuziga
momgbajxghotkhukyy
kjpapkwqueqjrhvzkxihfryybhungsb
dsusfrizvaiojfnuexdjpdjsldgtxjlabhuiyeiwfsmqackezoqqrzjefrxeckhfubouiwqpoffohqviglzzmkgtdf
fshk
ky
swzhlenbnfyv
lwmygstjytoqcbenzkhyjrjpgmcllyywwkwdfsofldvqgzfhlmfxfomldrwqrwm
jlqodhvqkqgsrnzecfbhvqtyhroaqdnzqgptnklzcurvhqzjx
rttmtcdkctprufxjamvllzfeunxwywzppudlwjvaemrzr
ktdierhmxcbuazrzr
tuvrdqrickjvbvohdvyljxpkuplnqevlbrcejvoofzlhvc
yxolglcsfrfsjkquljyrutiibh
kewafvoqdbvxjmcdwmvszerrbmbjnkfxpdxwanmdphcawfdutzovffmgupshzzfqfemfsbljin
guocoprjvyxdsmxcnxjec
qjhruqcibkc
nsfgdceaizofbcekiixyshqmxuwzebrrvy
zbebldssewxqefpczwuouokvvnmojkoknslyxdrdzqtdviixfelbvxwqlkeww
gkmtkjxbmyrhepqooxszynwwfjgmfcenothzegcrgwaklsybpt
piyloitapwgdmzmlesoxykzlxslyjeaznykbiedyclbolparhqqhcruzjgztkzszzeaikf
mrjbeydxhvpqxglwqtxldwddvjffunlggwjkuojdjyuiehewadjfzmkxysesfqalomxjagom
iukrbjresxghhffzjzgbzrqlqbowpccayprzyj
simzrtgrcfzehrwujxigmmiolxgkxrsqzgrqzyjedjik
ghldptrcegndmzbduteakwaiggorqyvwfizxcqbgwqjirmnlftmqqoyyumpknmguuftwxueumqeecupinbydpy
lnsvagbwbiqzgmeazugdyasgowgrnhv
upuwwysxgiymxcowyxbxxtflroffvcerranpyfohqnvprklqhmpghwszkzghbmyumnmlvaulppahbnzkbqrkmljzkrindjjqw
dryxenmgwovvy
nrhccsboklbnunftiimihtywzukv
ktfcah

kvfyyuulanwkcgsvequzarrmlwqngxgsunqsilgkyeuckoxpeuqgnjvyhlmnkugekwzshfcilyk
pkovgectnxsvkgkvcqzopygyfkgsltqcfexllbeyyyvlggglyfzngimnsuifpyhuefhpimqhmnuttaeuhfhpnvdislnhlxere
hmzzvmmphipnezsloijrqbefkreojicsvbtsphiwrzlvyehnmsgevnjfgowpyajvd
otmyrdzdzyjinxavbxkmcrcaibaswgwmbkmsomxpmixzfzwiwhxayzbgcdabjznmjahzoeoaplbwkxhi
ejedmnippjboynaawzoboqsbroorvwzbfghrtpjkymzybbzy
nbqets
jgqheqikwpdrgobeaadcbeaerbuxwoxfwnmbfxnbossvhubhwglaklgeocdkraspqgsvdfzua
phnqqmzcojp
newtqpviflrxjwfiqfzfmpyebx
piwlychrsxmdeyubhqirjnqobhogknmbwkmumulhtxmxxgagyjxhyqyaxogkculyhyst
AC output:

Code: Select all

23
16
8
27
5
17
20
4
11
5
11
9
20
24
9
15
3
15
14
3
13
20
20
2
4
9
21
0
9
9
15
8
24
20
9
23
7
20
1
15
18
12
9
5
25
11
8
6
12
7
5
6
21
8
4
15
8
3
24
8
25
27
3
17
16
16
16
8
21
5
4
12
12
3
10
18
12
21
16
13
7
15
1
6
12
8
10
3
12
18
14
18
13
5
0
28
21
4
5
10
Check input and AC output for thousands of problems on uDebug!

Mishi Rahman
New poster
Posts: 2
Joined: Sat Dec 07, 2013 4:33 pm

Re: 10405 - Longest Common Subsequence

Post by Mishi Rahman » Sat Dec 07, 2013 4:37 pm

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

long int c[1002][1002];
int d,e;
void LCS(char x[],char y[],int l,int k)
{
int i,j;
for(i=0;i<=l;++i)
c[0]=0;

for(j=0;j<=k;++j)
c[0][j]=0;

for(i=1;i<=l;++i)
for(j=1;j<=k;++j)
{
if(x==y[j])
c[j]=(c[i-1][j-1])+1;

else if(c[i-1][j]>=c[j-1])
c[j]=c[i-1][j];

else
c[j]=c[j-1];
}

printf("%ld\n",c[d][e]);
}

int main()
{
char x[1002],y[1002];
while(scanf("%s",x))
{
scanf("%s",y);
d=strlen(x);
e=strlen(y);

LCS(x,y,d,e);
}
return 0;
}

Mishi Rahman
New poster
Posts: 2
Joined: Sat Dec 07, 2013 4:33 pm

whats wrong with my code?? um getting TL!

Post by Mishi Rahman » Sat Dec 07, 2013 4:38 pm

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

long int c[1002][1002];
int d,e;
void LCS(char x[],char y[],int l,int k)
{
int i,j;
for(i=0;i<=l;++i)
c[0]=0;

for(j=0;j<=k;++j)
c[0][j]=0;

for(i=1;i<=l;++i)
for(j=1;j<=k;++j)
{
if(x==y[j])
c[j]=(c[i-1][j-1])+1;

else if(c[i-1][j]>=c[j-1])
c[j]=c[i-1][j];

else
c[j]=c[j-1];
}

printf("%ld\n",c[d][e]);
}

int main()
{
char x[1002],y[1002];
while(scanf("%s",x))
{
scanf("%s",y);
d=strlen(x);
e=strlen(y);

LCS(x,y,d,e);
}
return 0;
}

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

Re: 10405 - Longest Common Subsequence

Post by brianfry713 » Tue Dec 10, 2013 12:56 am

Read line by line instead of using scanf("%s"). The input may contain empty lines or spaces.
Check input and AC output for thousands of problems on uDebug!

Artifère
New poster
Posts: 4
Joined: Tue Mar 19, 2013 9:31 pm

Re: 10405 - Longest Common Subsequence

Post by Artifère » Wed Feb 15, 2017 3:53 pm

Hello!
[Edited: the problem was the Python recursion limit]

One of my student is trying to validate the exercise in Python with a code which returns all the correct values on the sets in uDebug and in this post. I cannot figure out what is wrong, I guess something Python-specific, but after a lot of tries, I got no improvement. The code gets WA. Could you give some help?

Post Reply

Return to “Volume 104 (10400-10499)”