## 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

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

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

#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

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

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

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

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

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

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

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

#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!

#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

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

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?