OJ Board

The Online Judge board
https://onlinejudge.org/board/

10405 - Longest Common Subsequence

https://onlinejudge.org/board/viewtopic.php?t=8864

Page 7 of 7

Re: 10405 - Longest Common Subsequence

Posted: Tue Dec 23, 2008 6:09 pm
by ashish_thakur
thanks for the insight I have corrected the flaw. It's accepted

Re: 10405 - Longest Common Subsequence

Posted: Sun Oct 31, 2010 4:46 pm
by sh415
getting frequent WA; dont know why...............
I have taken input through gets and then used LCS algorithm;
is there any thing critical or wrong?????

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

Posted: Sun Aug 14, 2011 6:31 am
by anan_xon
#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;
}

Re: 10405 - Longest Common Subsequence

Posted: Mon Aug 29, 2011 10:22 am
by limitedmage
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;
}

Re: 10405 - Longest Common Subsequence

Posted: Fri Dec 23, 2011 6:33 pm
by a.elbashandy
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;
}

Re: 10405 - Longest Common Subsequence

Posted: Tue Jan 10, 2012 4:32 pm
by davdigsb
you sure you posted it in the right section?

Re: 10405 - Longest Common Subsequence

Posted: Wed Jan 11, 2012 2:08 am
by brianfry713
http://en.wikipedia.org/wiki/Longest_co ... of_the_LCS

Re: 10405 - Longest Common Subsequence

Posted: Thu Oct 04, 2012 10:34 am
by vpanait
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

Re: 10405 - Longest Common Subsequence

Posted: Sun Apr 07, 2013 6:43 am
by moxlotus
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;
}

Re: 10405 - Longest Common Subsequence

Posted: Tue Apr 09, 2013 3:54 am
by brianfry713
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

Re: 10405 - Longest Common Subsequence

Posted: Sat Dec 07, 2013 4:37 pm
by Mishi Rahman
#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;
}

whats wrong with my code?? um getting TL!

Posted: Sat Dec 07, 2013 4:38 pm
by Mishi Rahman
#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;
}

Re: 10405 - Longest Common Subsequence

Posted: Tue Dec 10, 2013 12:56 am
by brianfry713
Read line by line instead of using scanf("%s"). The input may contain empty lines or spaces.

Re: 10405 - Longest Common Subsequence

Posted: Wed Feb 15, 2017 3:53 pm
by Artifère
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?
All times are UTC+02:00
Page 7 of 7

Powered by phpBB® Forum Software © phpBB Limited